Thread: 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.

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.

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.

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

thanks for your help

Dear Christopher
tnx for your advice , It really helped .

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.

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.

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.