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.

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

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

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

]]>thank you so much .]]>

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

thank you for your comment

could you please the method that I wrote above ? and tell me if it true

thanx

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.

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

]]>Hi everyone

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

]]>