Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

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

1. ## 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
```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```

2. ## 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.

3. ## The Following User Says Thank You to GregBrannon For This Useful Post:

CrazyCoder (November 2nd, 2013)

4. ## 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
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.

5. ## 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.

6. ## The Following User Says Thank You to ChristopherLowe For This Useful Post:

CrazyCoder (November 2nd, 2013)

7. ## 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 ...

```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;
}
}```

8. ## Re: determine the 1,000,000 th primitive number in less than 10 min !!!

Dear Christopher
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.

9. ## 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.

10. ## The Following User Says Thank You to GregBrannon For This Useful Post:

CrazyCoder (November 2nd, 2013)

11. ## Re: determine the 1,000,000 th primitive number in less than 10 min !!!

thanks , it helped . sorry for mistakes
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.

12. ## 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

13. ## The Following User Says Thank You to helloworld922 For This Useful Post:

GregBrannon (November 2nd, 2013)