Prime Numbers from Martyr2's Mega Project Ideas List

Page 1 of 1

1 Replies - 4076 Views - Last Post: 20 September 2010 - 05:19 PM

#1 s243a

Reputation: 1
• Posts: 137
• Joined: 17-March 10

Prime Numbers from Martyr2's Mega Project Ideas List

Posted 20 September 2010 - 12:14 AM

Coincidentally I recently looked though Martyr's suggested project earlier today and latter today was thinking about the problem:

Quote

Prime Factorization – Have the user enter a number and find all Prime Factors (if there are any) and display them.

Next Prime Number – Have the program find prime numbers until the user chooses to stop the asking for the next one.

I posted the following on another site:

Quote

The Chinese remainder theorem tells us that the system of equations:

\begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align}

Uniquely determines all numbers in the range:

$$X<N=n_1n_2\ldots n_k$$

and that all solutions are congruent modulo N.

The first four primes are congruent modulo 2. Moreover if something isn't congruent modulo 2 (that is it is not odd) then it is not a prime.

In the range N<6=2*3
All primes must be congruent to either 1 or 5 modulo 6=2*3 because these are the only two numbers in that range which aren't divisible by either 2 or 3.

Moreover, if a number isn't congruent to either 1 or 5 modulo 6 it is not a prime.

Now lets check the range of N<30=2*3*5

In this range all prime numbers will be one of the following and the only ones of these which aren't prime are dividable by 5.

1+6n 7,13,19,25
5+6n 11,17,23,29

We can check to see if a number n in this range (n<30) is prime by dividing by 6 and seeing if the remainder is either 1 or 5. Their are 11 primes less then 30 but we can check if a number is prime with one division and then a binary search on an array with two elements. Thus numbers less then 30 can be checked to see if they are prime with at most three operations.

Now lets check the range N<210=2*3*5*7

Choosing numbers which are less then 30, aren't dividable by 2,3, or 5 and congruent modulo 30:
1  + 30n = 31, 61, 91,  121, 151, 181
7  + 30n = 37, 67, 97,  127, 157, 187
11 + 30n = 41, 71, 101, 131, 161, 191
13 + 30n = 43, 73, 103, 133, 163, 193
17 + 30n = 47, 77, 107, 137, 167, 197
19 + 30n = 49, 79, 109, 139, 169, 199
23 + 30n = 53, 83, 113, 143, 173, 203
29 + 30n = 59, 89, 119, 149, 179, 209


The following product can be used to find numbers in this table which aren't prime:

$$x=7^{n1}11^{n2}13^{n3}19^{n4}23^{n5}29^{n6}$$

We do not need to consider divisibility by 2, 3 or 5 because all numbers in the table are relatively prime to 2, 3 and 5.

I wonder if anyone will find any flaws in my approach and I wonder how it compares to other approaches. I also wonder what the computational complexity of my approach is. For numbers less then 30 I can tell if something is prime with three operations which seems pretty good but how does it scale?

Is This A Good Question/Topic? 0

Replies To: Prime Numbers from Martyr2's Mega Project Ideas List

#2 s243a

Reputation: 1
• Posts: 137
• Joined: 17-March 10

Re: Prime Numbers from Martyr2's Mega Project Ideas List

Posted 20 September 2010 - 05:19 PM

So from the feedback I've gotten so far the method is well known but not as efficient as using a sieve. Further from the feedback I got the method is called prime wheels but I am not sure if this is correct because I am not sure if I communicated my algorithm well enough. Therefore I decided to try writing some preliminary code in java:

http://www.mymathfor...&p=60746#p60746
https://sourceforge....primefun/files/

but I still have some bugs and I have no idea how efficient it will be compared to other algorithms.