CODEWITHSUNDEEP
calgorithm
PJSingh
PJSingh

Reputation: 15

Optimized way for Finding prime numbers upto given value n

I am doing it by checking it from k=3 to n (given upper value) using this function for each value k. How can I optimize it to take all prime numbers till n in an array and not need to check for each number k?

int primeCheck(long long int k) {
    int j;
    int isPrime = 1;
    int sr = (int)sqrt(k);
    for (j = 2; j <= sr; j++) {
        if (k % j == 0) {
            //printf("=========== %d|%d\n", num,num2); // uncomment this to see if a number is divisible
            isPrime = 0; // this number is not prime, cos num can be divided by num2
            break;
        }
    }
    if (isPrime) {
        return isPrime; // reset the check parameter
    } else {
        return 0; // reset the check parameter
    }
    return 0;
}

Upvotes: 1

Views: 731

Answers (3)

Abbas Kararawala
Abbas Kararawala

Reputation: 1254

you can also skip even numbers after 2. something like

int primeCheck(long long int k){
    if(k<=1 || k%2==0){    //if number is even return 0 its not prime
        return 0;
    }

    int sr = (int) sqrt(k);    //probable divisor

    for(int j=3;j<=sr;j+=2){
        if(k%j == 0){
            //printf("=========== %d|%d\n", num,num2); // uncomment this to see if a number is divisable
            return 0; //if number is not prime skip everything and return zero
        }
    }
    return 1; //if loop completes i.e. not divisor found then return return 1
}

Upvotes: 0

Shubham
Shubham

Reputation: 2855

Try Sieve of Eratosthenes. This algorithm works by eliminating all the factors of a prime number from 2 to n. 

int main() {
    int n;
    scanf("%d", &n);
    int prime[n+1];
    for(int i = 0; i < n+1; i++)
        prime[i] = 0;

    for(int i = 2; i <= sqrt(n+1); i++) {
        if(prime[i] == 0) {
            for(int j = i*i; j <= n; j += i)
                prime[j] = 1;
        }
    }

    int prime_list[n], size = 0;
    for(int i = 2; i <= n; i++) {
        if(prime[i] == 0)
            prime_list[size++] = i;
    }
}

For example let the number initially be:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

  • Removing all multiples of 2(except 2) we get:

2 3 5 7 9 11 13 15 17 19 21 23 25 27 29

  • Removing all multiples of 3 (except 3), we get:

2 3 5 7 11 13 17 19 23 25 29

  • Removing all multiples of 5 (except 5), we get:

2 3 7 11 13 17 19 23 29

Now, there will be no more removals and after a few more iterations for each of the remaining prime numbers, this will be our final list.

The prime[i] for i = {2, 3, 7, 11, 13, 17, 19, 23, 29}. We will append all these indices to another prime_list vector as done in the code. This vector will give all the prime numbers from [2, n].

Upvotes: 2

Mojtaba Khooryani
Mojtaba Khooryani

Reputation: 1875

if you want to check a lot of numbers in a range I recommend Sieve of Eratosthenes algorithm.

your function could be better a bit:

int primeCheck(long long int n)
    {
        if (n <= 1)
        {
            return 0;
        }
        if (n <= 3)
        {
            return 1;
        }
        if (n % 2 == 0 || n % 3 == 0)
        {
            return 0;
        }
        int sr = (int)sqrt(n);

        for (int i = 5; i <= sr; i += 6)
        {
            if (n % i == 0 || n % (i + 2) == 0)
            {
                return 0;
            }
        }
        return 1;
    }

Upvotes: 0

Related Questions