how to know the number is prime or not buy using % ( mod )

Hannibal lecter · 2016-11-27 09:03:08

Hi,

how to know the number is prime or not buy using % ( mod )?

is there a simple way to know?

bobbym · 2016-11-27 09:11:24

Hi;

As far as I know, there is no simple way to know.

Hannibal lecter · 2016-11-27 09:38:48

I do that

for example :

7 , I add +1 to number 7

it will be "8" , when I do that I say after :

8%2=0 if it is true then the number is prime!

and the 7 it prime cause it is true

is that method right? or wrong?

bobbym · 2016-11-27 09:56:19

Try your method on 9.

Hannibal lecter · 2016-11-27 10:00:59

ops, it is not working hehehehehe, so..

what to do my teacher need an algorithm to find our the number prime or not

I know the AKS text,

but I need to use an method with "if"

like [ if (x%2=0) print " the number is even" ... etc

anyway thanks

bobbym · 2016-11-27 10:08:01

to find our the number prime or not

Your teacher is not the only one that could use a general algorithm.

How large are the numbers he wants it for?

Hannibal lecter · 2016-11-27 10:17:07

he did not specify, do you have a simple algorithm? he use java language be he don't want a program to run it
he want a simple algorithm,

is there?

bobbym · 2016-11-27 10:35:29

The wheel can use only one single mod to determine primality but it is limited in how big the numbers you can test. Also, you need to hold a very large number, which would be too big for Java.

There are probabilistic tests but they are not certain, just very likely to be prime.

danaj · 2016-12-02 04:42:33

If a number n is not prime, it must be divisible by some prime <= sqrt(n). So we can check divisibility by all primes up to and including floor(sqrt(n)). The mod operator returns the remainder of n % p after division, so if it returns 0, the number is evenly divisible by p.

E.g. is 57 prime? sqrt(57) is ~7.55 so we need to check all primes through 7. So check 2,3,5,7.

57 % 2 = 1. Continue.
57 % 3 = 0. Found a factor. The number is composite.

Random thoughts:

- remember to include sqrt(n) so we catch perfect squares.

- you can use a test p*p <= n instead of p <= sqrt(n). They each have gotchas in computer implementation: p*p can overflow in most languages, sqrt(n) is not exact in most languages, sqrt(n) is computationally expensive in most languages. The fastest method is to make a variable to store floor(sqrt(n)) before the loop, and make sure you use a good integer square root method. Most of this is moot if you're testing small numbers rather than near the 64-bit boundary.

- ideally we test just the primes, but you can compromise by testing 2 then odds, or 2,3,5 then a +2,+4 wheel (aka a mod-6 wheel), or a mod-30 wheel, etc.

- You can't use a single mod as a deterministic test. You could store lots of primes and do a lookup, which gives an O(1) algorithm making certain assumptions about hashes or O(log n) making other assumptions or using a binary search through a linear table. This doesn't work once the input is larger than your table, and it's terribly memory inefficient. I have seen it done for tiny values (e.g. to 256 or to ~30,000) just because the primes were there. I'm not convinced it is better even if the table exists.

This method is actually one of the fastest for tiny numbers, under a million or so. After that, other methods such as deterministic Miller-Rabin or BPSW are faster. Note that properly implemented for 64-bit inputs, they are *not* probabilistic, but completely correct. For numbers of 20+ digits, the trial division method above is really not practical. We can start using probabilistic and fast methods (e.g. BPSW, which has no known counterexamples), or proof methods.

I'm not sure why AKS got mentioned. If you understand AKS, then trial division should be a trivial concept. AKS is probably not something you want to actually use, as it's quite slow compared to other proof methods. Albeit it is fun to program if you like number theory.

bobbym · 2016-12-02 05:31:28

Hi;

Sorry, I meant to say GCD.

If you multiply all the primes that you have up to the sqrt of n, a single GCD will determine the primality of n. But for the reasons I gave, Java would need a multi-precision library.

danaj · 2016-12-02 20:42:40

You're right that we can do a gcd of a primorial, which is a way to do quite a bit of trial division in one "operation". For large inputs, it's actually quite effective in GMP. In that case I wasn't doing full trial division, just speeding up the "is the input divisible by a prime under 40,000" for instance.

Once of the primary advantages of this is that the primorial can be made once and re-used. This means it's a little trickier for small inputs since the included primes can exceed the input, but we could just use a different method for those.

Math Is Fun Forum

#1 2016-11-27 09:03:08

how to know the number is prime or not buy using % ( mod )

#2 2016-11-27 09:11:24

Re: how to know the number is prime or not buy using % ( mod )

#3 2016-11-27 09:38:48

Re: how to know the number is prime or not buy using % ( mod )

#4 2016-11-27 09:56:19

Re: how to know the number is prime or not buy using % ( mod )

#5 2016-11-27 10:00:59

Re: how to know the number is prime or not buy using % ( mod )

#6 2016-11-27 10:08:01

Re: how to know the number is prime or not buy using % ( mod )

#7 2016-11-27 10:17:07

Re: how to know the number is prime or not buy using % ( mod )

#8 2016-11-27 10:35:29

Re: how to know the number is prime or not buy using % ( mod )

#9 2016-12-02 04:42:33

Re: how to know the number is prime or not buy using % ( mod )

#10 2016-12-02 05:31:28

Re: how to know the number is prime or not buy using % ( mod )

#11 2016-12-02 20:42:40

Re: how to know the number is prime or not buy using % ( mod )

Board footer