determine the 1,000,000 th primitive number in less than 10 min !!!

Printable View

• November 2nd, 2013, 04:35 AM
CrazyCoder
determine the 1,000,000 th primitive number in less than 10 min !!!
how to calculate the 1,000,000 th prime number in less than 10 min in java language?
it's my code , but it is not as fast as I need ... , please give me the hints to improve it's speed and performance ;)
Code java:

```public class PrimeF {   private static boolean isPrime(long n) { long p=(long)Math.sqrt(n);   int i=2; while(i<=p) { int k=0; for(int j=2;j<=i;j++) if(i%j==0) k++; if(k==1) { if(n%i == 0) return false; } i++; }   return true; } public static long get_thPrime(int n) { int count=0,i=2; while(count < n) { if(isPrime(i)) count++; i++; }   return --i; } }//end class```

thanks for your help
• November 2nd, 2013, 05:06 AM
GregBrannon
Re: determine the 1,000,000 th primitive number in less than 10 min !!!
Please post your code in code or highlight tags. You can learn how in the Announcement topic at the top of the sub-forum.
• November 2nd, 2013, 05:32 AM
CrazyCoder
Re: determine the 1,000,000 th primitive number in less than 10 min !!!
Dear Greg , thanks for your help , if it's not clear again , let me know :)
Quote:

Originally Posted by GregBrannon
Please post your code in code or highlight tags. You can learn how in the Announcement topic at the top of the sub-forum.

• November 2nd, 2013, 05:45 AM
ChristopherLowe
Re: determine the 1,000,000 th primitive number in less than 10 min !!!
You don't need to check even numbers for primality. Return false if (n%2 == 0). Take that even further and check all the small factors.

Next up you will probably want to run Fermat's little theorem. It will tell you if the number is probably composite meaning you can quickly eliminate definite non-primes. If it picks up a composite you can do the brute force divisor check.

Realistically, this will only slightly reduce computational time. What you really need to do is the Sieve of Erathosethenes. The 1,000,000th prime is 15,485,863 so it's quiet a chunk of memory but it will only take a second or two.
• November 2nd, 2013, 05:47 AM
CrazyCoder
determine 1,000,000th primitive number in less than 10 minute !!!
how to calculate the 1,000,000 th prime number in less than 10 min in java language?
it's my code , but it is not as fast as I need ... , please give me the hints to improve it ...

Code java:

```public class PrimeF {   private static boolean isPrime(long n) { long p=(long)Math.sqrt(n);   int i=2; while(i<=p) { int k=0; for(int j=2;j<=i;j++) if(i%j==0) k++; if(k==1) { if(n%i == 0) return false; } i++; }   return true; } public static long get_thPrime(int n) { int count=0,i=2; while(count < n) { if(isPrime(i)) count++; i++; }   return --i; } }```
thanks for your help
• November 2nd, 2013, 05:52 AM
CrazyCoder
Re: determine the 1,000,000 th primitive number in less than 10 min !!!
Dear Christopher
tnx for your advice , It really helped .
Quote:

Originally Posted by ChristopherLowe
You don't need to check even numbers for primality. Return false if (n%2 == 0). Take that even further and check all the small factors.

Next up you will probably want to run Fermat's little theorem. It will tell you if the number is probably composite meaning you can quickly eliminate definite non-primes. If it picks up a composite you can do the brute force divisor check.

Realistically, this will only slightly reduce computational time. What you really need to do is the Sieve of Erathosethenes. The 1,000,000th prime is 15,485,863 so it's quiet a chunk of memory but it will only take a second or two.

• November 2nd, 2013, 06:00 AM
GregBrannon
Re: determine the 1,000,000 th primitive number in less than 10 min !!!
I believe those tags are quote tags, but you made the effort. Thanks. Please use the correct ones next time.

You're finding prime numbers, right? 'Prime' and 'primitive' are not the same thing.

You can start simplifying your algorithm by NOT checking even numbers. That's easy enough. Then you can skip multiples of 3 - getting more complicated - and you can extend that to eliminating all multiples of lesser prime numbers, also known as the Sieve of Eratosthenes.

Start by not checking even numbers and see if that helps.
• November 2nd, 2013, 06:04 AM
CrazyCoder
Re: determine the 1,000,000 th primitive number in less than 10 min !!!
thanks , it helped . sorry for mistakes :D
Quote:

Originally Posted by GregBrannon
I believe those tags are quote tags, but you made the effort. Thanks. Please use the correct ones next time.

You're finding prime numbers, right? 'Prime' and 'primitive' are not the same thing.

You can start simplifying your algorithm by NOT checking even numbers. That's easy enough. Then you can skip multiples of 3 - getting more complicated - and you can extend that to eliminating all multiples of lesser prime numbers, also known as the Sieve of Eratosthenes.

Start by not checking even numbers and see if that helps.

• November 2nd, 2013, 12:42 PM
helloworld922
Re: determine the 1,000,000 th primitive number in less than 10 min !!!
I have a few posts about implementing the sieve of Eratosthenes efficiently:

Optimizing the Sieve of Eratosthenes

One problem using the raw sieving technique is that the sieve asks the question "what are all the primes less than n?", rather than the question you're interested in which is "what is the nth prime?"

You have some options:

1. Estimate roughly how large the nth prime should be:

The number of primes less than n is roughly 1.25506 * n / log(n)

2. Use a segmented sieve of Eratosthenes. This sieves in chunks, and you can keep adding more segments dynamically until you've reached the number of primes you want.

There are a few additional optimizations you can make to the segmented sieve, such as adding wheel factorization, though this really isn't necessary if you just want to just get the 1 millionth prime. My implementation can generate all primes less than 1 billion in ~3.5 seconds (about 57 million primes). Actually, this isn't my fastest implementation nor is it anywhere near the fastest implementation on the web. My fastest implementation is under 3 seconds (don't remember the exact timing), and the current fastest implementation can do it in a fraction of a second.

Segmented Sieve of Eratosthenes with Wheel Factorization
primesieve - current fastest prime number sieve