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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

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

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

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

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

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

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

Offline

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

A= all the primes below

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

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

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,752

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

Offline

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

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

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

Offline

Pages: **1**