-
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; 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's takes 141
Mine takes 594ms to find all primes <10000, Lamesy's takes 703
Mine takes 41125 to find all primes <100000, Lamsey's takes 8641.
So, it looks like mine is faster for relatively small tasks, but Lamesy's is quicker for larger tasks...
Interestingly, removing the printline statement from Lamesy's (for when the number is not prime), brings his execution time for primes <100000 down to 3532ms, less than half...
I've got to say his is better than mine :)
-
After tweaking Lamesy's code further, I'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'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