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

You are not logged in.

#1 2016-03-13 02:58:19

Primenumbers
Member
Registered: 2013-01-22
Posts: 127

Fast way to find primes.

Take your number, p, which you want to find out if it's prime or not.
Square root it. Multiply all the primes below the square root together.
Minus p from this number and see if there are any common factors between the two. If there is p is not prime, if there isn't p is prime.

Example:

p=51
square root p=7ish
2*3*5*7=210
210-51=159 common factor=3
51 is not prime

p=53
square root p=7ish
2*3*5*7=210
210-53=157 no common factors
53 is prime.

Note: It is impossible if the two numbers add up to a no. factorable by everything, for one to be factorable by a number and the other not. They must either both be factorable or both not.


"Time not important. Only life important." - The Fifth Element 1997

Offline

#2 2016-03-13 04:53:58

Primenumbers
Member
Registered: 2013-01-22
Posts: 127

Re: Fast way to find primes.

I'm not sure but I'm guessing this would be a faster way to compute finding primes. I.e. using Euclid's algorithm.
See............ 

      https://en.wikipedia.org/wiki/Euclidean_algorithm


"Time not important. Only life important." - The Fifth Element 1997

Offline

#3 2016-03-13 20:41:47

mathaholic
Member
From: Earth
Registered: 2012-11-29
Posts: 3,251

Re: Fast way to find primes.

I see the technique. I tried it in several numbers and it worked.


Mathaholic | 10th most active poster | Maker of the 350,000th post | Person | rrr's classmate
smile

Offline

#4 2016-03-13 23:53:11

Primenumbers
Member
Registered: 2013-01-22
Posts: 127

Re: Fast way to find primes.

 

A= all the primes below

    multiplied together
If (A-p) and p do not share a common factor then p = prime.


"Time not important. Only life important." - The Fifth Element 1997

Offline

#5 2016-03-14 01:13:45

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 107,663

Re: Fast way to find primes.

This is called the wheel.


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.

Online

#6 2016-10-22 09:49:22

Lehona
Member
Registered: 2016-10-22
Posts: 16

Re: Fast way to find primes.

Primenumbers wrote:

I'm not sure but I'm guessing this would be a faster way to compute finding primes. I.e. using Euclid's algorithm.
See............ 

      https://en.wikipedia.org/wiki/Euclidean_algorithm

Primality Tests are usually done on numbers in the range of 2^1024 to 2^2048 (or much, much bigger numbers, when it's simply about "finding a prime", not crypto). Enumerating (and multiplying!) all the primes below those numbers is an insurmountable task.

If enumerating all primes was easy, RSA would be useless :-p

Edit: I just saw this thread is kinda old (still first page), I hope this doesn't count as necromancy smile

Last edited by Lehona (2016-10-22 09:50:03)

Offline

Board footer

Powered by FluxBB