This content has been marked as final.
Show 28 replies

1. Re: Finding if a number is prime
800322 Nov 1, 2006 10:11 AM (in response to 807591)Does anyone have codes snippets that can find if a
Sure. Ptretty common homework.
number is a Prime or not?
I'll be glad to have such code.
I can tell. What do you need it for? 
2. Re: Finding if a number is prime
abillconsl Nov 1, 2006 10:19 AM (in response to 807591)You can check out [url http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm#_The_Obvious_Method_for_Finding_Primes]Fun With Prime Numbers 
3. Re: Finding if a number is prime
807591 Nov 1, 2006 10:21 AM (in response to abillconsl)you can tell if a number is prime if its not divisible by any number less then itself except for 1. 
4. Re: Finding if a number is prime
807591 Nov 1, 2006 10:27 AM (in response to 807591)How fast does it run. There are many many faster ways to do this.....depending on the range of numbers you're working on....but here's a simple way to do it. This is more of a number theory question, not a java question.
public static void main(String[] args) { long number = 465464623; long result = isPrime( number ); System.out.println( result != 1 ? "Is not prime....divisible by " + result : "PRIZIME" ); } private static long isPrime(long x) { for ( int i = 2; i < Math.sqrt( x ); i++ ) { if ( x % i == 0 ) { return i; } } return 1; }

5. Re: Finding if a number is prime
807591 Nov 1, 2006 10:27 AM (in response to 807591)you can tell if a number is prime if its not
Don't even need to chack that many numbers.
divisible by any number less then itself except for 1. 
6. Re: Finding if a number is prime
doremifasollatido Nov 1, 2006 10:33 AM (in response to 807591)
Once you check for divisibility by 2, you only need to test odd numbers.you can tell if a number is prime if its not
Don't even need to chack that many numbers.
divisible by any number less then itself except for 1. 
7. Re: Finding if a number is prime
807591 Nov 1, 2006 10:35 AM (in response to doremifasollatido)
Actually....you only need to ever check divisability by prime numbers up to the square root of the number. If you want to brute force it.
for 1.you can tell if a number is prime if its not
divisible by any number less then itself exceptDon't even need to chack that many numbers.
Once you check for divisibility by 2, you only need
to test odd numbers. 
8. Re: Finding if a number is prime
800282 Nov 1, 2006 10:47 AM (in response to 807591)Norweed, your method is incorrect. Take any prime number and multiply it with itself. These numbers will pass your test as being prime as well.
@OP: here's a nice method to test numbers for primatlity:public boolean isPrime(long number) { return new java.math.BigInteger(String.valueOf(number)).isProbablePrime(100); }

9. Re: Finding if a number is prime
807591 Nov 1, 2006 10:51 AM (in response to 800282)Norweed, your method is incorrect. Take any prime
Make it <=....no biggy. isProbablePrime won't tell you if it's prime or not...only if it's likely a prime.
number and multiply it with itself. These numbers
will pass your test as being prime as well.
@OP: here's a nice method to test numbers for
primatlity:public boolean isPrime(long number) { return new java.math.BigInteger(String.valueOf(number)).isProbab ePrime(100); }

10. Re: Finding if a number is prime
800282 Nov 1, 2006 11:01 AM (in response to 807591)> Make it <=....no biggy.
Of course it's a biggy. The first method returns wrong answers.
> isProbablePrime won't tellyou if it's prime or not...only if it's likely a
prime.
I know what probable means. 
11. Re: Finding if a number is prime
807591 Nov 1, 2006 11:08 AM (in response to 800282)> Make it <=....no biggy.
Anal buggers all over the place. I didn't unit test it for squares of primes...just typed something up and threw it out there...sorry for the lack of testing and reflection on all code I post.....good catch, but i was refering to the mistake as not being that big of a deal. I wasn't infering that it worked or anything.
Of course it's a biggy. The first method returns
wrong answers.
> isProbablePrime won't tellyou if it's prime or not...only if it's likely a
prime.
I know what probable means. 
12. Re: Finding if a number is prime
JosAH Nov 1, 2006 11:12 AM (in response to 807591)
Better yet, make it:Norweed, your method is incorrect. Take any prime
Make it <=....no biggy. isProbablePrime won't tell
number and multiply it with itself. These numbers
will pass your test as being prime as well.
@OP: here's a nice method to test numbers for primatlity:> > public boolean isPrime(long number) { return new java.math.BigInteger(String.valueOf(number)).isProbabePrime(100); }
you if it's prime or not...only if it's likely a prime.
btw, for simple 32 bit ints the probablePrime method is exact.for ( int i = 2; i*i <= x ); i++ )
kind regards,
Jos 
13. Re: Finding if a number is prime
800282 Nov 1, 2006 11:17 AM (in response to 807591)> Anal buggers all over the place.
?
Where did I call you names?
> I didn't unit testit for squares of primes...just typed something up
and threw it out there...sorry for the lack of
testing and reflection on all code I post.....
Never said you should. A lot of the code I post contains (design) errors.
> good catch, but i was refering to the mistake as not beingthat big of a deal. I wasn't infering that it worked
or anything.
I though you meant by "no biggy" that it didn't really matter if the squared prime's weren't labelled as prime.
Why the hostility? 
14. Re: Finding if a number is prime
JosAH Nov 1, 2006 11:30 AM (in response to 807591)I didn't unit test it for squares of primes...just typed something up
So don't do that. Software development is an exact and precise process.
and threw it out there...
It's a science actually. Sloppy code jamming is worse than no code at all.
Jos