CODEWITHSUNDEEP
c++
brainst
brainst

Reputation: 291

How far can I go with this program of computing prime numbers?

#include <iostream>

using namespace std;

int ifprime(long long int);
int main()

{
    long long int number;   
    cout<<"Enter the number of prime numbers you want to know:\n";
    cin>>number;    //number is the number of prime numbers to be displayed
    long long int j=0;
    long long int m=2;      //m would be used as consecutive natural numbers on which, test of prime number is performed

    while (1<2)
    {
        if(ifprime(m)==1)
        {
            j+=1;   // j is the counter of the prime numbers found and displayed
            cout<<m<<endl;
        }
        m+=1;
        if(j==number)
        {
            break;
        }
    }

}

int ifprime(long long int a)
{
    for(int i=2;i<a;i++)
    {
        if(a%i==0)
        {
            return 0;
        }
    }
    return 1;
}

The range of long long int seems to be small compared to the biggest primes known :/

Even if I were to compute the last prime number in the range of the long long int , can I compute the time it would take to compute that number?

Upvotes: 2

Views: 146

Answers (1)

CookedCthulhu
CookedCthulhu

Reputation: 787

Let's say the biggest prime number was n = 13. Your program would then try the following numbers: 2, 3, 4,.. 11, 12 So you have to test your number n - 2 times (which is more or less n times) and until you reach that point your program has to go through 2, 3, 4, ... 11, 12, 13, which is also (more or less) n times. -->The complexity is O(n^2). Simple tip to speed up your program: store every prime number you've found so far in std::vector and only try these. This way you avoid integer factorization (like dividing with 6 (2 * 3) or 8 (2 * 2 * 2)).

Upvotes: 1

Related Questions