Calculate Million Primes

Question

I have one question to print a million prime numbers. I wrote a java program for this. It currently takes 1.5 minutes to calculate it. I think my solution is not so effective. I used the bottom algorithm:

• First add 1 2 3 to the first list
• Calculation of the last digit of the checked number
• Check if the digit is 0, 2 or 4 or 6 or 8, and then skip the number
• otherwise, calculate the square root of the number.
• Trying to divide a number starting from 2 to the square root of
• if the number is divisible and then the number is missing, adding it to the main list

I also read a few other solutions, but I did not find a good answer. Please suggest, ideally, that there should be a minimum time to calculate this and what changes are needed to make the algorithm more efficient.

Answer 1

A simple sieve of Eratosthenes works as clappers. This calculates the 1,000,000th number per second less than on my box:

class PrimeSieve { public List<int> Primes; private BitArray Sieve; public PrimeSieve(int max) { Primes = new List<int> { 2, 3 }; // Must include at least 2, 3. Sieve = new BitArray(max + 1); foreach (var p in Primes) for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true; } public int Extend() { var p = Primes.Last() + 2; // Skip the even numbers. while (Sieve[p]) p += 2; for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true; Primes.Add(p); return p; } } 

EDIT: Screening starts optimally with p ^ 2 rather than 2p, as Will Ness correctly points out (all compound numbers below p ^ 2 will be noted in earlier iterations).

Answer 2

If you added 1 to your list, your answer is no longer right :)

In any case, the Sieve of Eratosthenes is where you should start, it is incredibly simple and effective enough.

Once you are familiar with the idea of ​​sieves and how they work, you can move on to Sieve Atkin , which is a bit more complicated, but obviously more effective.

Answer 3

Key things:

• Skip all even numbers. Start with 5 and just add two at a time.
• 1 is not a prime ...
• Check the number by typing mod of all primes to the square root of the number. There is no need to test anything but simple ones.

Answer 4

You might want to implement the Sieve of Eratosthenes algorithm to find primes from 1 to n and iteratively increase the range while you do if necessary. (i.e. not yet found 1,000,000 primes)

Answer 5

Here is the Ocaml program, which implements the Test sieve division (which is a kind of inverse for Eratosthenes, as correctly indicated by Will):

 (* Creates a function for streaming integers from x onward *) let stream x = let counter = ref (x) in fun () -> let _ = counter := !counter + 1 in !counter;; (* Filter the given stream of any multiples of x *) let filter sx = fun () -> let rec filter' () = match s () with n when n mod x = 0 -> filter' ()| n -> n in filter' ();; (* Get next prime, apply a new filter by that prime to the remainder of the stream *) let primes count = let rec primes' count' s = match count' with 0 -> []| _ -> let n = s () in n :: primes' (count' - 1) (filter sn) in primes' count (stream 1);; 

It works with a stream of integers. Each time a new prime number is opened, a filter is added to the stream, so that the remainder of the stream is filtered from any multiple of that prime. This program can be modified to generate primes on demand.

In Java, it should be pretty easy to use the same approach.

Hope this helps!

Answer 6

First, 1 is not a prime.

Secondly, the millionth number is 15,485,863, so you need to be prepared for some data processing.

Thirdly, you probably want to use the Sieve of Eratosthenes; here is a simple version:

 function sieve(n) bits := makeArray(0..n, True) for p from 2 to n step 1 if bits[p] output p for i from p*p to n step p bits[i] := False 

This may not work for the size of the array, which you will need to calculate the first millions of primes. In this case, you will want to implement a segmented sieve of eratosthenes.

I did a great job with simple numbers on my blog, including essay , which provides an optimized Eratosthenes sieve, with implementations in five programming languages.

No matter what you do, with any programming language, you should be able to calculate the first millions of primes in no more than a few seconds.

Answer 7

Here's a javascript solution that uses recursion and iteration to reach the millionth number. This is not as fast as the Erafosthenes sieve, but does not require knowing in advance the value of the millionth simple (i.e. the size of the required sieve):

 function findPrimes(n, current, primes) { if (!n || current < 2) return [] var isPrime = true for (var i = 0; i < primes.length; i++) { if (current % primes[i] == 0) { isPrime = false break } } if (isPrime) primes.push(current) if (primes.length < n) return findPrimes(n, current + 1, primes) else return primes } var primes = [2,3] for (var i = 1; i <= 1000; i++) { primes = findPrimes(i*1000, primes[primes.length - 1]+1, primes) console.log(i*1000 + 'th prime: ' + primes[primes.length-1]) } process.exit() 

Output:

 ... 996000th prime: 15419293 997000th prime: 15435941 998000th prime: 15452873 999000th prime: 15469313 1000000th prime: 15485863 Process finished with exit code 0 

Answer 8

As a more recent level, I will try this one, so any improvement to make it more efficient and faster is appreciated

  public static void main(String ar[]) { ArrayList primeNumbers = new ArrayList(); for(int i = 2; primeNumbers.size() < 1000000; i++) {//first 1 million prime number // for(int i = 2; i < 1000000; i++) {//prime numbers from 1 to 1 million boolean divisible = false; for(int j=2;j<i/2;j++){ if((i % j) == 0) { divisible = true; break; } } if(divisible == false) { primeNumbers.add(i); // System.out.println(i + " "); } } System.out.println(primeNumbers); } 

Answer 9

Not everyone after 5, ending in five, divisible by 5, so you can skip things that are right (1, numb) <> "5", for example 987,985. I made one in Excel that will check a million numbers for primes and spit them out in a column in about 15 seconds, but it goes crazy about 15 million.