Java Prime Number Finder...

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

---

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

---

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

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.

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.");
    }
  }
}

---

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 :(

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

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 :o

edit:

Code:

---

public class lamseycode
{
  public static void main(String[] args)
  {
    boolean prime;
    double start_time, end_time;
    start_time = System.currentTimeMillis();
    for (int number = 1; number < 1000; number += 2)
    {
      prime = true;
      for (int x = 3; x <= (number / 2); x += 2)
      {
        if(number % x == 0)
        {
          prime = false;
          break;
        }
      }
      if (prime)
      System.out.println(number+" is prime.");
     }
     end_time = System.currentTimeMillis();
     System.out.println("Time taken = "+(end_time - start_time));
   }
}

---

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 :o :lol: :o

Code:

---

public class lamsey
{
  public static void main(String[] args)
  {
    boolean prime;
    int primes = 0;
    double start_time = System.currentTimeMillis();
    for (int number = 1; number < 10000; number += 2)
    {
      prime = true;
      for (int x = 3; x <= (number / 2); x += 2)
      {
        if(number % x == 0)
        {
          prime = false;
          break;
        }
      }
      if (prime)
        primes++;
     }
     double end_time = System.currentTimeMillis();
     System.out.println("Time taken = "+(end_time - start_time));
     System.out.println("Primes found = "+primes);
   }
}

---

Great, now you have a program with no output. Very useful. :rolleyes:

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

Quote:

---

Originally posted by Lamsey@31 March 2004 - 14:28
Great, now you have a program with no output. Very useful. :rolleyes:

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

---

Well, the point of removing the output was that it now shows you just how long it takes to calculate them, not to display them...

Besides, if you wanted to show them, you could always output to text file...

This code outputs the results to a text file, only slowing the program down by about 0.15 seconds for all primes < 100000 :D

Code:

---

import java.util.*;
import java.io.*;

public class lamsey
{
  public static void main(String[] args) throws Exception
  {
    File outFile = new File("primes.txt");
        FileOutputStream outFileStream = new FileOutputStream(outFile);
        PrintWriter outStream = new PrintWriter(outFileStream);
    
    boolean prime;
    int primes=0;
    double start_time=System.currentTimeMillis();
    System.out.println("Working...please wait");
    for (int number=1;number<100000;number+=2)
    {
      prime=true;
      for (int x=3;x<=number/2;x+=2)
      {
        if(number%x==0)
        {
          prime=false;
          break;
        }
      }
      if(prime)
      {
        primes++;
        outStream.println(number+" is a prime number");
      }
    }
    double end_time = System.currentTimeMillis();
    System.out.println("Time taken = "+(end_time - start_time));
    System.out.println("Primes found = "+primes);
  }
}

---

This code is a little bit quicker than mine and Lamesy&#39;s attempts so far:

Code:

---

import java.lang.*;

class sieve
{
        public static void main (String [] args)
    {
  final int max = 100000;
        final int startat = 1;
        int n = max;
        double limit;
        double start_time=0, end_time=0;
        int primesfound=0;
        start_time = System.currentTimeMillis();
      
        boolean numberpool [] = new boolean [n];
        for(int i=2; i<n; i++)
        {
                numberpool[i]=true;
        }

        limit = Math.sqrt(n);
        int j=2;
        for (int i=j+j; i<n; i=i+j)
        {
                numberpool[i]=false;
        }

        for (j=3; j<=limit; j=j+2)
        {
                if (numberpool[j]==true)
                {
          for (int i=j+j; i<n; i=i+j)
          {
                  numberpool[i]=false;
             }
            }
        }

        System.out.println("Prime Numbers from " + startat + " to " + max + ":");
        for (int i=startat; i<max; i++)
        {
                if (numberpool[i]==true)
                {
          primesfound++;
            }
        }
        end_time = System.currentTimeMillis();
        System.out.println("Time taken = "+(end_time - start_time));
        System.out.println("Number of primes found "+primesfound);
    }
}

---

I should say it&#39;s not my code (well, I never wrote it anyway), but here are a few results:

Prime Numbers from 1 to 100000:
Time taken = 16.0ms
Number of primes found 9592

Prime Numbers from 1 to 1000000:
Time taken = 94.0ms
Number of primes found 78498

Prime Numbers from 1 to 10000000:
Time taken = 860.0ms
Number of primes found 664579

:o