How can I write a program that finds prime numbers up to 1 million?

Question

prime numbers

Answer 1

You just need to divide every number with each number from 2 to its square root (after square root will be just multiples of already tried divisors). Here is the program:

#include <iostream>
#include <cmath>

using namespace std;

bool is_prime(int n);

int main() {
for(int i = 1; i <= 1000000; i++)
if(is_prime(i))
cout << i << " ";
return 0;
}

bool is_prime(int n) {
int square_root = (int)sqrt(n);
for(int i = 2; i <= square_root; i++) {
if(n % i == 0)
return false;
}
return true;
}

Answer 2

Calculating primes one by one will be slow.The time complexity is O(n sqrt(n)). We can implement sieve of erastothenes with a boolean array to optimize the code. This reduces the time complexity to O(N) and all primes can be accessed after the calculation.
#include<iostream>
#include<cmath>
#define MAXN 1000000
bool composite[MAXN];
int main() {
int stop=sqrt(MAXN);
for(int i=2;i<=stop;i++) {
if(composite[i]) continue;
for(int j=i*i;j<=MAXN;j+=i)
composite[j]=true;
}
}
Afterwards, members which is still false will be a prime number :)

Of course, if you need to have the prime numbers only, you can store them into another dynamic array like vector instead of the original one.

Answer 3

thank you for answers