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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 9 of 9

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

  1. #1
    Junior Member
    Join Date
    Jul 2013
    Posts
    7
    Thanks
    5
    Thanked 0 Times in 0 Posts

    Question 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



    thanks for your help
    Last edited by CrazyCoder; November 2nd, 2013 at 06:18 AM. Reason: clarifying


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default 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. #3
    Junior Member
    Join Date
    Jul 2013
    Posts
    7
    Thanks
    5
    Thanked 0 Times in 0 Posts

    Default 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 View Post
    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. #4
    Forum VIP
    Join Date
    Jun 2011
    Posts
    317
    My Mood
    Bored
    Thanks
    47
    Thanked 89 Times in 74 Posts
    Blog Entries
    4

    Default 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. #5
    Junior Member
    Join Date
    Jul 2013
    Posts
    7
    Thanks
    5
    Thanked 0 Times in 0 Posts

    Default 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;
    	}
    }
    thanks for your help

  8. #6
    Junior Member
    Join Date
    Jul 2013
    Posts
    7
    Thanks
    5
    Thanked 0 Times in 0 Posts

    Default 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 View Post
    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. #7
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default 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. #8
    Junior Member
    Join Date
    Jul 2013
    Posts
    7
    Thanks
    5
    Thanked 0 Times in 0 Posts

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

    thanks , it helped . sorry for mistakes
    Quote Originally Posted by GregBrannon View Post
    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. #9
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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)

Similar Threads

  1. Replies: 2
    Last Post: July 1st, 2012, 11:48 AM
  2. PHP Developer - OOP / MVC / XML / JSON - £40,000 (NEG)
    By JacquelineRobbins in forum Paid Java Projects
    Replies: 0
    Last Post: January 12th, 2012, 06:58 AM

Tags for this Thread