Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 146
Website

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

Hi,

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

is there a simple way to know?


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

Hi;

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 146
Website

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

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?


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

Try your method on 9.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 146
Website

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

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


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 146
Website

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

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?


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

danaj
Member
Registered: 2014-03-03
Posts: 29

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

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.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

danaj
Member
Registered: 2014-03-03
Posts: 29

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

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.

Offline

Board footer

Powered by FluxBB