1 2 Previous Next 28 Replies Latest reply on Apr 2, 2008 6:53 AM by EJP

# Finding if a number is prime

hello,

Does anyone have codes snippets that can find if a number is a Prime or not?

I'll be glad to have such code.

Regards,
Socx
• ###### 1. Re: Finding if a number is prime
Does anyone have codes snippets that can find if a
number is a Prime or not?
Sure. Ptretty common homework.
I'll be glad to have such code.
I can tell. What do you need it for?
• ###### 3. Re: Finding if a number is prime
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
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
you can tell if a number is prime if its not
divisible by any number less then itself except for 1.
Don't even need to chack that many numbers.
• ###### 6. Re: Finding if a number is prime
you can tell if a number is prime if its not
divisible by any number less then itself except for 1.
Don't even need to chack that many numbers.
Once you check for divisibility by 2, you only need to test odd numbers.
• ###### 7. Re: Finding if a number is prime
you can tell if a number is prime if its not
divisible by any number less then itself except
for 1.
Don't even need to chack that many numbers.
Once you check for divisibility by 2, you only need
to test odd numbers.
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.
• ###### 8. Re: Finding if a number is prime
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
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)).isProbab
ePrime(100);
}``````
Make it <=....no biggy. isProbablePrime won't tell you if it's prime or not...only if it's likely a prime.
• ###### 10. Re: Finding if a number is prime
> Make it <=....no biggy.

Of course it's a biggy. The first method returns wrong answers.

> isProbablePrime won't tell
you 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
> Make it <=....no biggy.

Of course it's a biggy. The first method returns

> isProbablePrime won't tell
you if it's prime or not...only if it's likely a
prime.

I know what probable means.
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.
• ###### 12. Re: Finding if a number is prime
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)).isProbabePrime(100);
}``````
Make it <=....no biggy. isProbablePrime won't tell
you if it's prime or not...only if it's likely a prime.
Better yet, make it:
``for ( int i = 2; i*i <= x ); i++ )``
btw, for simple 32 bit ints the probablePrime method is exact.

kind regards,

Jos
• ###### 13. Re: Finding if a number is prime
> Anal buggers all over the place.

?
Where did I call you names?

> 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.....

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 being
that 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
I didn't unit test it for squares of primes...just typed something up
and threw it out there...
So don't do that. Software development is an exact and precise process.
It's a science actually. Sloppy code jamming is worse than no code at all.

Jos
1 2 Previous Next