Return all primes smaller than M

Question

Given that the integer M. returns all primes smaller than M.

Give the algorithm as good as you can. The complexity of time and space must be taken into account.

Can anyone skip? Appreciate!

Answer 1

A few additional tips:

• You only need to check the square root of n , since each composite number has at least one prime factor that is less than or equal to its square root
• You can cache known primes when creating them and check subsequent numbers only for numbers in this list (instead of each number below sqrt(n) )
• Obviously you can skip even numbers

Answer 2

The Eratosthenes sieve is a good place to start.

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

Answer 3

Eratosthenes sieve is good.

Answer 4

π (n) count numbers less than or equal to n. Pafnutny Chebyshev showed that if

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

exists, it is 1. In fact, there are many values ​​that are approximately equal to π (n), as shown in the table.

It gives the correct number of primes for this number format. I hope this will be helpful.

Answer 5

the usual answer is to implement the Sieve of Eratosthenes , but this is really just a solution for finding a list of all primes smaller than N. If you want strength tests for specific numbers, for large numbers.

Answer 6

I am a novice programmer in C # (and new to SO), so this may be a bit detailed. However, I tested this and I am working.

Here is what I came up with:

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

Answer 7

You can do this using a bottom-up dynamic programming approach called the eratosthenes sieve. Basically, you create a logical cache of all numbers up to n, and you mark each multiple of each number as not_prime. Further optimization can be achieved by checking only upto sqrt (n), since any composite number will have at least one divisor less than 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 Save Eratosthenes. Of course, there will be better implementations.

// finds the number of primes less than the 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

Atkin's sieve is also the best algorithm to implement in this case, and it only accepts O (N) and O (N) operations. Please refer to https://en.wikipedia.org/wiki/Sieve_of_Atkin for a detailed explanation of the algorithm and pseudocode.