Your Ad Here Your Ad Here
Page 1 of 2 12 LastLast
Results 1 to 10 of 13

Thread: Java Prime Number Finder...

  1. #1
    Poster
    Join Date
    Jan 2004
    Posts
    3,110
    I started writing (badly ) a prime number finder in java code today...below is where I'm at just now, however, it returns "4" as a prime number (which it obviously isn't), however, I can't sort it for the correct "4" output without either breaking the program or 'cheating' by starting > 4. Anyone got any ideas?

    Code:
    public class primefinder
    {
    	public static void main(String[] args)
    	{
      int count1 = 0;
      int count2 = 0;
      
      for(int number=2; number<50; number++)
      {
        count1 = 0;
        for(int i=2; i<number/2; i++)
        {
           count2 = 0;
         if(number%2 == 0.0)
         {
              count2++;
              break;
            }
         else  
         {
           if(number%i == 0.0)
            count1++;
            }
        }
        if(count1 == 0 && count2 == 0)
          System.out.println(number+" is a prime number");
      }
        }
    }
    On a given day or given circumstance, you think you have a limit.
    And you then go for this limit and you touch this limit and you think "Ok, this is the limit".
    As soon as you touch this limit, something happens and you suddenly can go a little bit further.
    With your mind power, your determination, your instinct and the experience as well, you can fly very high.

    - Ayrton Senna, R.I.P.

  2. Software & Hardware   -   #2
    Retired
    Join Date
    Dec 2003
    Posts
    1,124
    Code:
    public boolean isPrime(long number)
     {
       if ((number % 2 == 0) && (number != 2))
         return false;
       long endNum = (long)Math.sqrt((double)number);
       long curNum = 3;
       long remainder;
       while (curNum <= endNum)
       {
         remainder = number % curNum;
         if (remainder == 0)
           return false;
         curNum += 2;
       }
       return true;
     }

  3. Software & Hardware   -   #3
    Poster
    Join Date
    Jan 2004
    Posts
    3,110
    Nice program! Did you write it?
    Sadly mine works at finding prime numbers from a range of inputs (i.e. find all prime numbers from 2 - 1000), rather than checking whether an inputted number is prime...

    edit: just saw your edit
    On a given day or given circumstance, you think you have a limit.
    And you then go for this limit and you touch this limit and you think "Ok, this is the limit".
    As soon as you touch this limit, something happens and you suddenly can go a little bit further.
    With your mind power, your determination, your instinct and the experience as well, you can fly very high.

    - Ayrton Senna, R.I.P.

  4. Software & Hardware   -   #4
    I tried briefly
    Code:
    for (number = (a + (a % 2)); number <= b&#59; number+2)
    {
    	max = (number - (number % 2)) / 2   // round down &  halve 
             max = max - 1 + (max % 2)  // To make it odd 
    	for (denominator = max; denominator >= 3; denominator - 2)
    	{
     *if number % denominator = 0 
     *{	
     *	break
     *}
     *
     *if denominator ==3 
     *	prime found ...
    	}
    }
    doesn't find primes 1,2,3 but i think it should work after that, obviously its not written in proper code. I didn't really understand what you meant about '4' thing...

    Even if you ignore the rest of my code, adding 2s judiciously instead of ++ will save you code and runtime.

  5. Software & Hardware   -   #5
    Ex-member
    Join Date
    Jan 2003
    Posts
    5,529
    Here's mine:
    Code:
    /* Returns the prime numbers from 2 to 100000
     *
     * By Lamsey
     */
    public class PrimeFinder
    {
      public static void main(String[] args)
      {
        boolean prime;
        for (int number = 2; number < 1000001; number++)
        {
          prime = true;
          if ((number % 2) == 0)
            prime = false;
          else
          {
            for (int x = 3; x <= (number / 2); x += 2)
            {
              if ((number % x) == 0)
              {
                prime = false;
                break;
              }
            }
          }
          if (prime)
          	System.out.println(number+" is prime.");
          else
          	System.out.println(number+" is not prime.");
        }
      }
    }

  6. Software & Hardware   -   #6
    Poster
    Join Date
    Jan 2004
    Posts
    3,110
    My finished one:

    Code:
    public class primefinder
    {
    	public static void main(String[] args)
    	{
      int count1 = 0;
      int count2 = 0;
      long start_time = 0, end_time = 0;
      
      start_time = System.currentTimeMillis();
      
      for(int number=2; number<1000; number++)
      {
        count1 = 0;
        
        for(int i=2; i<=number/2; i++)
        {
           count2 = 0;
         if(number%2 == 0.0)
         {
              count2++;
              break;
            }
         else  
         {
           if(number%i == 0.0)
            count1++;
            }
        }
        if(count1 == 0 && count2 == 0)
          System.out.println(number+" is a prime number");
      }
      System.out.println("Finished");
      end_time = System.currentTimeMillis();
      System.out.println("Time taken = "+(end_time - start_time));	
        }
    }
    Sorry, ilw, but I never understood what you said
    On a given day or given circumstance, you think you have a limit.
    And you then go for this limit and you touch this limit and you think "Ok, this is the limit".
    As soon as you touch this limit, something happens and you suddenly can go a little bit further.
    With your mind power, your determination, your instinct and the experience as well, you can fly very high.

    - Ayrton Senna, R.I.P.

  7. Software & Hardware   -   #7
    Poster
    Join Date
    Jan 2004
    Posts
    3,110
    Mine takes 31ms to find all primes <1000, Lamesy&#39;s takes 141
    Mine takes 594ms to find all primes <10000, Lamesy&#39;s takes 703
    Mine takes 41125 to find all primes <100000, Lamsey&#39;s takes 8641.

    So, it looks like mine is faster for relatively small tasks, but Lamesy&#39;s is quicker for larger tasks...

    Interestingly, removing the printline statement from Lamesy&#39;s (for when the number is not prime), brings his execution time for primes <100000 down to 3532ms, less than half...

    I&#39;ve got to say his is better than mine
    On a given day or given circumstance, you think you have a limit.
    And you then go for this limit and you touch this limit and you think &quot;Ok, this is the limit&quot;.
    As soon as you touch this limit, something happens and you suddenly can go a little bit further.
    With your mind power, your determination, your instinct and the experience as well, you can fly very high.

    - Ayrton Senna, R.I.P.

  8. Software & Hardware   -   #8
    Poster
    Join Date
    Jan 2004
    Posts
    3,110
    After tweaking Lamesy&#39;s code further, I&#39;ve just seen 16ms execution for primes <1000 and the average is around about 20-23ms, which is pretty quick

    edit:

    Code:
    public class lamseycode
    {
     &nbsp;public static void main&#40;String&#91;&#93; args&#41;
     &nbsp;{
     &nbsp; &nbsp;boolean prime;
     &nbsp; &nbsp;double start_time, end_time;
     &nbsp; &nbsp;start_time = System.currentTimeMillis&#40;&#41;;
     &nbsp; &nbsp;for &#40;int number = 1; number &#60; 1000; number += 2&#41;
     &nbsp; &nbsp;{
     &nbsp; &nbsp; &nbsp;prime = true;
     &nbsp; &nbsp; &nbsp;for &#40;int x = 3; x &#60;= &#40;number / 2&#41;; x += 2&#41;
     &nbsp; &nbsp; &nbsp;{
     &nbsp; &nbsp; &nbsp; &nbsp;if&#40;number % x == 0&#41;
     &nbsp; &nbsp; &nbsp; &nbsp;{
     &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;prime = false;
     &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;break;
     &nbsp; &nbsp; &nbsp; &nbsp;}
     &nbsp; &nbsp; &nbsp;}
     &nbsp; &nbsp; &nbsp;if &#40;prime&#41;
     &nbsp; &nbsp; &nbsp;System.out.println&#40;number+&#34; is prime.&#34;&#41;;
     &nbsp; &nbsp; }
     &nbsp; &nbsp; end_time = System.currentTimeMillis&#40;&#41;;
     &nbsp; &nbsp; System.out.println&#40;&#34;Time taken = &#34;+&#40;end_time - start_time&#41;&#41;;
     &nbsp; }
    }
    On a given day or given circumstance, you think you have a limit.
    And you then go for this limit and you touch this limit and you think &quot;Ok, this is the limit&quot;.
    As soon as you touch this limit, something happens and you suddenly can go a little bit further.
    With your mind power, your determination, your instinct and the experience as well, you can fly very high.

    - Ayrton Senna, R.I.P.

  9. Software & Hardware   -   #9
    Poster
    Join Date
    Jan 2004
    Posts
    3,110
    After taking out all printline statements (just running a count on the number of primes) and using Lamsey&#39;s code, the execution time for primes <10000 (ten thousand, as compared to 1000 in the last post) is now 47ms

    Code:
    public class lamsey
    {
     &nbsp;public static void main&#40;String&#91;&#93; args&#41;
     &nbsp;{
     &nbsp; &nbsp;boolean prime;
     &nbsp; &nbsp;int primes = 0;
     &nbsp; &nbsp;double start_time = System.currentTimeMillis&#40;&#41;;
     &nbsp; &nbsp;for &#40;int number = 1; number &#60; 10000; number += 2&#41;
     &nbsp; &nbsp;{
     &nbsp; &nbsp; &nbsp;prime = true;
     &nbsp; &nbsp; &nbsp;for &#40;int x = 3; x &#60;= &#40;number / 2&#41;; x += 2&#41;
     &nbsp; &nbsp; &nbsp;{
     &nbsp; &nbsp; &nbsp; &nbsp;if&#40;number % x == 0&#41;
     &nbsp; &nbsp; &nbsp; &nbsp;{
     &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;prime = false;
     &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;break;
     &nbsp; &nbsp; &nbsp; &nbsp;}
     &nbsp; &nbsp; &nbsp;}
     &nbsp; &nbsp; &nbsp;if &#40;prime&#41;
     &nbsp; &nbsp; &nbsp; &nbsp;primes++;
     &nbsp; &nbsp; }
     &nbsp; &nbsp; double end_time = System.currentTimeMillis&#40;&#41;;
     &nbsp; &nbsp; System.out.println&#40;&#34;Time taken = &#34;+&#40;end_time - start_time&#41;&#41;;
     &nbsp; &nbsp; System.out.println&#40;&#34;Primes found = &#34;+primes&#41;;
     &nbsp; }
    }
    On a given day or given circumstance, you think you have a limit.
    And you then go for this limit and you touch this limit and you think &quot;Ok, this is the limit&quot;.
    As soon as you touch this limit, something happens and you suddenly can go a little bit further.
    With your mind power, your determination, your instinct and the experience as well, you can fly very high.

    - Ayrton Senna, R.I.P.

  10. Software & Hardware   -   #10
    Ex-member
    Join Date
    Jan 2003
    Posts
    5,529
    Great, now you have a program with no output. Very useful.

    I really wanted to know if 95,247 was prime or not

Page 1 of 2 12 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •