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

You are not logged in.

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

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

prime numbers `

wave
Hi everyone

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

Offline

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

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

Re: prime numbers `

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

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: prime numbers `

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

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

Re: prime numbers `

hi bobbym

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

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: prime numbers `

Where did you get it?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

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

Re: prime numbers `

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

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: prime numbers `

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

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

Re: prime numbers `

by the way
thank you so much .

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: prime numbers `

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

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

Re: prime numbers `

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

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

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

Re: prime numbers `

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

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: prime numbers `

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

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

Re: prime numbers `

Hi y'all smile

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


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

Board footer

Powered by FluxBB