Benedict Irwin edited Primality.tex  over 9 years ago

Commit id: 7dc3c39bf8274a6752fb424645c3ceeb5e43167c

deletions | additions      

       

\hline  1;mn & \mathrm{div} \; \mathrm{by} \\  \hline  1;n\in\mathbb{Z} & 1 \\ & 1\\  1;2n\in\mathbb{Z} & 11 \\ & 11\\  1;3n\in\mathbb{Z} & 3,37 \\ 3×37 & 111\\  1;4n\in\mathbb{Z} & 101 \\ & 101\\  1;5n\in\mathbb{Z} & 41,271 \\ 41×271 & 1;5\\  1;6n\in\mathbb{Z} & 13 \\  1;7n\in\mathbb{Z} & 239,4649 239×4649 & 1;7  \\ 1;8n\in\mathbb{Z} & 73 \\  1;9n\in\mathbb{Z} & 3^2,333667 \\ 3^2×333667 & 3003003\\  1;10n\in\mathbb{Z} & 9091 \\ & 9091\\  1;11n\in\mathbb{Z} & 21649,513239 21649×513239 & 1;11  \\ 1;12n\in\mathbb{Z} & 9901 \\ & 9901\\  1;13n\in\mathbb{Z} & 53,79,265371653 \\ 53×79×265371653 & 1;13\\  1;14n\in\mathbb{Z} & 909091 \\ & 909091\\  1;15n\in\mathbb{Z} & 2906161 \\  1;16n\in\mathbb{Z} & 5882353 \\  1;17n\in\mathbb{Z} & 2071723×5363222357 \\ & 1;17\\  1;18n\in\mathbb{Z} & 52579?? \\  1;19n\in\mathbb{Z} & 1;19 \\ & 1;19\\  1;20n\in\mathbb{Z} & 27961 \\  1;21n\in\mathbb{Z} & 10838689 \\  1;22n\in\mathbb{Z} & 513239 \\  1;23n\in\mathbb{Z} & 1;23 & 1;23\\  1;24n\in\mathbb{Z} & 99990001 99990001\\  1;25n\in\mathbb{Z} & 21401×25601×182521213001 & 100001000010000100001\\  1;50n\in\mathbb{Z} & 251×5051×78875943472201 & 99999000009999900001\\  \hline  \end{array}  \end{equation} 

To find more factors, one could use the previously found factors to quickly divide the number.  For example if we wanted to find the prime factors of $1;50$, [given the previously foudn information of up to $1;25$], we may look at the divisors of $50$, $1,2,5,10,25,50$, and identify that the prime factorisation of $1;50$ will be $11×41×271×9091×21401×25601×182521213001xF$, $11×41×271×9091×21401×25601×182521213001×F$,  where $F$ are the associated divisors with $n=50$. We know $1;50$ is not prime, as $50$ is not prime. We learn frommthis calculation that $F=99999000009999900001$ which is not prime but is of our $9,0,+1$ form... This gives $251×5051×78875943472201$ for $1;50n\in\mathbb{Z}$.  Task: construct a sieve of Sieve of Eratosthenes style algorithm which uses this concept as a test for primality?