Return all prime numbers smaller than M

Question

Given an integer M. return all prime numbers smaller than M.

Give a algorithm as good as you can. Need to consider time and space complexity.

Answer 1

The Sieve of Eratosthenes is a good place to start.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 2

A couple of additional performance hints:

1. You only need to test up to the square root of M, since every composite number has at least one prime factor less than or equal to its square root
2. You can cache known primes as you generate them and test subsequent numbers against only the numbers in this list (instead of every number below sqrt(M))
3. You can obviously skip even numbers (except for 2, of course)

Answer 3

Sieve of Eratosthenes is good.

Answer 4

The usual answer is to implement the Sieve of Eratosthenes, but this is really only a solution for finding the list of all prime numbers smaller than N. If you want primality tests for specific numbers, there are better choices for large numbers.

Answer 5

i'm a novice programmer in c# (and new to S.O.), so this may be a bit verbose. nevertheless, i've tested this, and i works.

this is what i've come up with:

for (int i = 2; i <= n; i++)
{
    while (n % i == 0)
    {
        Console.WriteLine(i.ToString());
        n /= i;
    }
}
Console.ReadLine();

Answer 6

π(n) count the primes less than or equal to n. Pafnuty Chebyshev has shown that if

limn→∞ π(n)/(n/ln(n))

exists, it is 1. There are a lot of values that are approximately equal to π(n) actually, as shown in the table.

It gives right number of prime number for this number format.I hope this will be helpful.

Answer 7

You can do it using a bottom up dynamic programming approach called the Sieve of Eratosthenes Basically you create a boolean cache of all numbers upto n and you mark each the multiples of each number as not_prime. Further optimizations can be gained by checking only upto sqrt(n) since any composite number will have at least one divisor less that sqrt(n)

    public int countPrimes(int n) {
    if(n==0){
        return 0;
    }else{
        boolean[] isPrime=new boolean[n];
        for(int i=2;i<n;i++){
            isPrime[i]=true;
        }

        /* Using i*i<n instead of i<Math.sqrt(n)
         to avoid the exepnsive sqrt operation */
        for(int i=2;i*i<n;i++){
           if(!isPrime[i]){
               continue;
           }
            for(int j=i*i;j<n;j+=i){
                isPrime[j]=false;
            }
        }

        int counter=0;
        for(int i=2;i<n;i++){
            if(isPrime[i]){
                counter++;
            }
        }

        return counter;

    }
}

Answer 8

This is what I developed for Seive of Eratosthenes. There would be better implementations,of course.

//finds number of prime numbers less than length

private static int findNumberOfPrimes(int length) {
    int numberOfPrimes = 1;
    if (length == 2) {
        return 1;
    }

    int[] arr = new int[length];
    //creating an array of numbers less than 'length'
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i + 1;
    }
    //starting with first prime number 2, all the numbers divisible by 2(and upcoming) is replaced with -1
    for (int i = 2; i < arr.length && arr[i] != -1; i++) {

        for (int j = i; j < arr.length; j++) {
            if (arr[j] % arr[i] == 0) {
                arr[j] = -1;
                numberOfPrimes += 1;
            }
        }

    }
    return numberOfPrimes;
}

Answer 9

The Sieve of Atkin is also the best algorithm to implement in this case and it takes only O(N) operations and O(N) space. Please refer https://en.wikipedia.org/wiki/Sieve_of_Atkin for detailed explanation of the algorithm and pseudocode.