New Topic/Question
Reply
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.
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:
[tex]\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}
[/tex]
Uniquely determines all numbers in the range:
[tex] X<N=n_1n_2\ldots n_k[/tex]
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:
The following product can be used to find numbers in this table which aren't prime:
[tex]x=7^{n1}11^{n2}13^{n3}19^{n4}23^{n5}29^{n6}[/tex]
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.
[tex]\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}
[/tex]
Uniquely determines all numbers in the range:
[tex] X<N=n_1n_2\ldots n_k[/tex]
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:
[tex]x=7^{n1}11^{n2}13^{n3}19^{n4}23^{n5}29^{n6}[/tex]
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.
http://www.physicsfo...ad.php?t=430566
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?
MultiQuote
| 