To be frank, all the approaches in this thread are really bad for the question. Let me Give a step by step tutorial on prime numbers that atleast everyone should know.
1. Noob method
Code:
#include<iostream>
using namespace std;
bool isPrime(int n)
{
if(n == 1)
return false;
if(n == 2)
return true;
for(int i=2;i<n;i++)
if(n%2 == 0)
return false;
return true;
}
int main()
{
int sum = 0;
int limit = 2000000;
for(int i=2;i<=limit;i++)
{
if(isPrime(i))
sum += i;
}
cout<<sum<<endl;
}
No need to explain this.
Actual Time Taken : Don't have that much patience!
Time complexity: O(n^2) (Really Bad!)
2. Some obvious improvements
Code:
#include<iostream>
using namespace std;
bool isPrime(int n)
{
if(n == 1)
return false;
if(n == 2)
return true;
if(n%2 == 0)
return false;
for(int i=3;i<n/2;i+=2)
if(n%i == 0)
return false;
return true;
}
int main()
{
int sum = 2;
int limit = 2000000;
for(int i=3;i<=limit;i+=2)
{
if(isPrime(i))
sum += i;
}
cout<<sum<<endl;
}
Checking Only odd numbers for divisibility with odd numbers. (Note: I have maintained the universality of the isPrime())
In words, If a number is divisible by 2, it is simply not prime unless it is 2 itself. Moreover, if it is not divisible by 2, it is not divisible by any multiple of 2 (2*x) as well.
Also, if it is not divisible by 2, it won't be divisible by any number > n/2 as well (I will generalize this in the next step).
Actual Time Taken : Don't have that much patience!
Time complexity: Still O(n^2) with slightly lesser constant (Really Bad!)
3. Some real Improvement
Code:
#include<iostream>
#include<cmath>
using namespace std;
bool isPrime(int n)
{
if(n == 1)
return false;
if(n == 2)
return true;
int lt = n;
for(int i=2;i<=lt;i++, lt=n/i)
if(n%i == 0)
return false;
return true;
}
int main()
{
int sum = 2;
int limit = 2000000;
for(int i=3;i<=limit;i+=2)
{
if(isPrime(i))
sum += i;
}
cout<<sum<<endl;
}
Notice that isPrime() first assumes that the number is prime, then tries to find a case where it is contradicted. Thus, it will run till it finds a divisor for
n. In the last point, I made an optimization that if
n is not divisible by 2, we can reduce the upper bound to
n/2. Why not do the same for other numbers as well. If in isPrime(), if the loop is at say, i=x and it doesn't divide
n, then we can say that
n is not divisible by any number 2,3,4,5....,x. Thus, we can safely reduce the upper bound to
n/x. This drastically reduces the Time requirements.
Actual Time Taken : 1.478s
Time complexity: O(n*sqrt(n)) (Not Bad!)
4. Improvising the previous approach
The previous isPrime() can be written as
Code:
#include<iostream>
#include<cmath>
using namespace std;
bool isPrime(int n)
{
if(n == 1)
return false;
if(n == 2)
return true;
int lt = sqrt(n);
for(int i=2;i<=lt;i++)
if(n%i == 0)
return false;
return true;
}
In last point, as
i increases by 1,
lt decreases to
lt/i. So where does they meet?
i<=n/i => i*i<=n => i<=sqrt(n).
Actual Time Taken : 0.780s
Time complexity: O(n*sqrt(n)) with reduced constant (Not Bad!)
5. Real Stuff
0.780s is not bad, right?
Wrong! It is a really BAD solution for such questions. It is fine if we had to check some numbers for primality, but for generating primes, this algo is bad for the given limits.
We can exploit one thing in the isPrime() for such prime generation problems. One question, if you checked a number for divisibility by 3, why do you need to check for multiples of 3? i.e, generalize the following optimization we did -
If a number is not divisible by 2, we need not check for its divisibility by even numbers (2*x)
The generalization is, Only check divisibility by prime numbers. We can implement this by making sure that, while checking for
x for prime, we already know all previous discovered primes and if
x is found to be prime, we store it for future use.
Code:
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
vector<int> primes;
bool isPrime(int n)
{
if(n==1)
return 0;
int limit=sqrt(n);
for(int i=0;i<primes.size() && primes[i]<=limit;i++)
if(n%primes[i]==0)
return false;
return true;
}
void generatePrimes(int n)
{
primes.push_back(2);
for(int i=3;i<=n;i+=2)
{
if(isPrime(i))
{primes.push_back(i);}
}
}
int main()
{
int limit = 2000000;
int sum = 0;
generatePrimes(limit);
for(int i=0;i<primes.size();i++)
sum += primes[i];
cout<<sum<<endl;
}
Actual Time Taken : 0.370s
Time complexity: O(n*P(sqrt(n))) with really less constant, P(x) = number of primes less than x (GREAT! since in worst case P(sqrt(2*10^6)) = 223)
6. Even Better
Half of times, the above method works for me. I prefer above method because I derived it myself
but there is a more popular and simpler method called sieve of Sieve of Eratosthenes.
I won't explain this as I am getting bored. But it is really simple to understand. Sieve of Eratosthenes - Wikipedia, the free encyclopedia
Code:
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int sieve[2000001];
void generatePrimes()
{
for(int i=2;i<2000001;i++)
{
if(!sieve[i])
{
if(1LL*i*i<2000001LL)
for(int j=i*i;j<2000001;j+=i)
sieve[j] = 1;
}
}
}
int main()
{
int sum = 0;
generatePrimes();
for(int i=2;i<2000001;i++)
if(!sieve[i])
sum += i;
cout<<sum<<endl;
}
Actual Time Taken : 0.081s
Time complexity: O(n*loglogn) (Excellent!)
and hence it won't work. My code will work only if iterated through N and then counted (My earlier code).
