Find all primes less than N

general
,
1

Below is my implementation for finding all primes less than 1e6. But for some reason, I get a WA with this code. Is something wrong here?

set<int> prime;
prime.insert(2);
prime.insert(3);
for(int i = 6; i < 1e6 + 7; i+=6)
{   
    prime.insert(i - 1);
    prime.insert(i + 1);
}

If it’s wrong, what is the best method to do this?

[EDIT] Apart from Seive of Eratosthenes.

1 Like
2

I don’t think this will be true for every i. I think seive is the best method. eg 35 and 37

3

Clearly, it doesn’t work when i=24, as i+1=25 which isn’t a prime number. :slight_smile:

1 Like
4

Sieve of Eratosthenes

5

Sieve of Eratosthenes is the best way.
Time complexity is O(nloglogn)
space complexity is O(n)

6

Right. So every prime number if of the form 6n + 1 or 6n - 1, but not the other way round.

1 Like
7

Go through the first answer here maths

1 Like
8

Sieve of Sundaram is the best one for finding and print all prime number less than N

1 Like
9

what is the complexity of Sieve of sundaram…Instead of this u can use Sieve of Eratosthenes (Nloglogn) or linear sieve (N) or wheel factorisation (N/loglogN) …

10

Use linear sieve :slight_smile: (I don’t know how complexity is O(N) but yeah it’s better )

bool composite[MAX+1];
vi primes;

void LinearSieve(){
    //0 means prime , 1 means non prime
    memset(composite,0,sizeof(composite));

    for(int i=2;i<=MAX;i++)
    {
        if(!composite[i])
            primes.push_back(i);

        for(int j = 0 ;  j < sz(primes) and i*primes[j] <= MAX; j++)
        {
            composite[primes[j]*i]=1;

            if(i%primes[j]==0)break;
        }

    }
}
11

Yeah, this is what I ended up using. This should be O(n\text{log }n).

12

N(log(logn)) ?

13

Yes my bad. It’s O(n log(log(n))).

14

yeah it’s for sieve of Eratosthenes :slight_smile:

1 Like
15

I didn’t know about linear Sieve. Thanks!

1 Like
16

Instead of taking int array , use bool array , to find out whether a number is prime or not , in case of sieve of eratosthenes … it is fast and efficient and u can make array of bool upto 108

bool prime[MAX+1];

void sieve1(){ //prime or not
    for(int i=0;i<=MAX;i++) prime[i]=1;

    prime[0]=prime[1]=0;

    for(lli i=4;i<=MAX;i+=2) prime[i]=0;

    for (int p=3; p*p<=MAX; p+=2){
        if (prime[p] == 1)
            for (int i=p*2; i<=MAX; i += p){
                prime[i] = 0;
            }
      }
}
2 Likes
17

Thanks! I’m not very comfortable with questions involving number of divisors and prime number checks. Hope this helps with that. :v:

1 Like
18

Every prime number greater than 3 is of the form 6n+1 or 6n-1. The converse is not true. Use sieve of Eratosthenes or just modify your code a bit.
Add a check prime function. We assume that n > 3.

bool isPrime(int n)
{
    bool flag = 1;
    for (int i = 2; i*i <= n; ++i)
    {
        if (n % i == 0)
        {
            flag = 0;
            break;
        }
    }
    return flag;
}
set <int> prime;
prime.insert(2);
prime.insert(3);
for(int i = 6; i < 1e6 + 7; i+=6)
{   
    if (isPrime(i-1)) prime.insert(i - 1);
    if (isPrime(i+1)) prime.insert(i + 1);
}

The complexity will be O(n(\sqrt{n}+\log{n})) because isPrime() is O(\sqrt{n}) and insertion in a set takes O(\log{n}) but sieve of Eratosthenes is only O(n\log{(\log{n})}) which is much more fast.

I’d suggest using sieve rather than this approach (or remove the set and use a vector with push_back()).

1 Like
19

Thanks! I had used a set because that was within limits. Anyways the best thing to do is a bool array, with O(1) lookup, I guess.

1 Like