prime numbers `

FERMAT'S · 2011-02-27 13:23:43

Hi everyone

could u please write me the methods those to know if the number is prime number ?

FERMAT'S · 2011-02-27 13:29:56

I read one before that says .
if X is integer
to know if X is prime or not .
First find a square number that is biger tahn X and let's call it y ^2
so
root(x ) <y

second, divide X on all the square number between 2 - y
now , if the result is integer number so X is not prime . if it is not so x is a prime number .

I hope if this right .

Last edited by FERMAT'S (2011-02-27 13:31:03)

bobbym · 2011-02-27 13:48:32

Hi;

Is this what you are trying?

http://en.wikipedia.org/wiki/Fermat%27s … ion_method

There are lots of methods to factor numbers but none of them are very fast for large numbers. That method in the link is a method discovered by Fermat. There is also trial division. Their are quadratic sieve methods, wheel methods, elliptic curve methods etc. Except for trial division and Fermats method they are all complicated.

FERMAT'S · 2011-02-27 18:24:42

hi bobbym

thank you for your comment
could you please the method that I wrote above ? and tell me if it true
thanx

bobbym · 2011-02-27 18:33:13

Where did you get it?

FERMAT'S · 2011-02-27 18:39:12

I knew it from someone .
and I read it again in a Teaching Package.
but I don't have this package now > so I want to be sure aout this infornmation.

Last edited by FERMAT'S (2011-02-27 18:40:06)

bobbym · 2011-02-27 18:42:04

That is what I can not give you. The fermat's method on the Wikipedia page is well known, the one you are asking about looks like it but I am not sure. It could be a modification of the standard fermats method, there are a couple of improvements. But I do not recognize it.

FERMAT'S · 2011-02-27 18:44:32

by the way
thank you so much .

bobbym · 2011-02-27 18:49:05

Hi;

Are you doing some calculations with that algorithm? Supposing that method works. It still is very inefficient. I think the one on Wikipedia is a better way to do it.

X on all the square number between 2 - y

Are you saying divide X by all the squares between 2 and y? Or all the primes form 2 - y? Which is just trial division.

sweetpeaenc · 2011-03-01 00:59:48

Hi, prime numbers are basically numbers which you can only divide 1 and itself into. E.G 7 is a prime number, 2 is a prime number you can decide easily if a number is prime by using a sieve of eratosthenes. (putting numbers on a grid and crossing off the even numbers and the ones that can be divided by other numbers) Remember though that 1 is not a prime and 2 is! Hope I helped a little bit.

tangent · 2011-03-01 23:44:25

The quickest way to know whether a number is prime aside from using the sieve of eratosthenes method is:
1. Find the square root of the number (e.g. 179, square root of 179 is approximately 13)
2. Try to divide 179 by any of the prime numbers up to 13 in this case, so use 7, 11 and 13 only.
Definitely if the number ends in 5, then it's composite, and if the sum of the digits of the given number is a multiple of 3, then it's divisible by three
3. Since in my example, 7, 11 and 13 does not divide 179, then 179 is prime.

Note, all even numbers greater than 2 are composite numbers, and only numbers ending in 1, 3, 7 or 9 are possible prime, but mostly not.

Make sure to always check whether it's divisible by 3 first up to the nearest square root of the given number.

bobbym · 2012-08-08 22:07:42

Hi tangent;

That is only considered the quickest way for very small numbers. There arer much better ways for larger numbers. The elliptic curve method and the quadratic sieve are two of them.

noelevans · 2012-08-09 04:53:00

Hi y'all

To just find out whether a number n is prime or not, one of the fastest methods is as follows:

In the following b is any base: 2,3,4,5,... preferably a prime. I usually use 2 and do the
calculations on Maple.

Calculate b^(n-1) mod n. If this turns out to be 1, then the chances are overwhelming
that it is prime. The exceptions are called Carmichael numbers and they are they are few
and far between. The first two are 651 and 1105.
41041 is the eleventh Carmichael number. The factors of a psuedoprime have to be "just right"
for them to produce a 1 in this calculation.

Google Carmichael Number to see several articles about this. Some of these articles should tell
how to determine whether of not you have a Carmichael number.

If n is a Carmichael number and gcd(n,b)>1 then the mod will not be 1.
There are only 8241 Carmichael numbers less than 10^12. That's 8.241*10^(-7) %.

So this mod test is a quick test to determine primality with a high degree of probability.
You might also Google the Miller-Rabin test for primality. (There's a Wiki article.)

Primality is much easier and faster to determine than doing a factorization.

Math Is Fun Forum

#1 2011-02-27 13:23:43

prime numbers `

#2 2011-02-27 13:29:56

Re: prime numbers `

#3 2011-02-27 13:48:32

Re: prime numbers `

#4 2011-02-27 18:24:42

Re: prime numbers `

#5 2011-02-27 18:33:13

Re: prime numbers `

#6 2011-02-27 18:39:12

Re: prime numbers `

#7 2011-02-27 18:42:04

Re: prime numbers `

#8 2011-02-27 18:44:32

Re: prime numbers `

#9 2011-02-27 18:49:05

Re: prime numbers `

#10 2011-03-01 00:59:48

Re: prime numbers `

#11 2011-03-01 23:44:25

Re: prime numbers `

#12 2012-08-08 22:07:42

Re: prime numbers `

#13 2012-08-09 04:53:00

Re: prime numbers `

Board footer