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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**FERMAT'S****Member**- Registered: 2011-01-17
- Posts: 29

Hi everyone

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

Offline

**FERMAT'S****Member**- Registered: 2011-01-17
- Posts: 29

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)*

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,661

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.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**FERMAT'S****Member**- Registered: 2011-01-17
- Posts: 29

hi bobbym

thank you for your comment

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

thanx

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,661

Where did you get it?

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**FERMAT'S****Member**- Registered: 2011-01-17
- Posts: 29

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)*

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,661

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.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**FERMAT'S****Member**- Registered: 2011-01-17
- Posts: 29

by the way

thank you so much .

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,661

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.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**sweetpeaenc****Member**- Registered: 2011-02-28
- Posts: 12

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.

I am colourful and unique no doubt about it!

Offline

**tangent****Member**- Registered: 2011-02-28
- Posts: 3

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.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,661

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.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**noelevans****Member**- Registered: 2012-07-20
- Posts: 236

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.

Writing "pretty" math (two dimensional) is easier to read and grasp than LaTex (one dimensional).

LaTex is like painting on many strips of paper and then stacking them to see what picture they make.

Offline

Pages: **1**