Games · Awards · About · Blog · Press Kit · Contact
Prime Factorizations

Friday, November 17, 2017
By: Matthew Doucette

In doing a simple coding exercise with NSCC Game Development students, we explored prime factorization of numbers -- which is factorization of numbers down to their prime factors. An example factorization of 100 is 25 x 4, however the prime factorization of 100 can only be 2 x 2 x 5 x 5 (all primes).

 

Sample Results:

1: ...
2: PRIME
3: PRIME
4: 2, 2.
5: PRIME
6: 2, 3.
7: PRIME
8: 2, 2, 2.
9: 3, 3.
10: 2, 5.
11: PRIME
12: 2, 2, 3.
13: PRIME
14: 2, 7.
15: 3, 5.
16: 2, 2, 2, 2.
17: PRIME
18: 2, 3, 3.
19: PRIME
20: 2, 2, 5.
...

 

Most Numbers Are Not Prime. Why?

Most numbers divide into small primes and large primes. It is almost as if these large primes is what makes them not prime, in the sense that they are almost 'in the way'.

Here's an analysis starting at the largest integer 64-bits can store, 18,446,744,073,709,551,615, and counting downward:

18446744073709551615: 3, 5, 17, 257, 641, 65537, 6700417.
18446744073709551614: 2, 7, 7, 73, 127, 337, 92737, 649657.
18446744073709551613: 13, 3889, 364870227143809.
18446744073709551612: 2, 2, 3, 715827883, 2147483647.
18446744073709551611: 11, 59, 98818999, 287630261.
18446744073709551610: 2, 5, 23, 53301701, 1504703107.
18446744073709551609: 3, 3, 818923289, 2502845209.
18446744073709551608: 2, 2, 2, 2305843009213693951.
18446744073709551607: 7, 9241, 464773, 613566757.
18446744073709551606: 2, 3, 71, 42013, 1030686124187.
18446744073709551605: 5, 2551, 1446236305269271.
18446744073709551604: 2, 2, 37, 9902437, 12586817029.
18446744073709551603: 3, 139, 2306123, 19182323033.
18446744073709551602: 2, 157, 1973, 29775769179641.
18446744073709551601: 53, 348051774975651917.
18446744073709551600: 2, 2, 2, 2, 3, 3, 5, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321.
18446744073709551599: 19, 67, 14490765179661863.
18446744073709551598: 2, 17, 17, 17, 2927, 641387128649.
18446744073709551597: 3, 6148914691236517199.
18446744073709551596: 2, 2, 34421, 133978850655919.
...

See the next 5,000+ numbers in this sequence:

Notice how many divide into large prime numbers? All of them except 18,446,744,073,709,551,600 = 2 x 2 x 2 x 2 x 3 x 3 x 5 x 5 x 7 x 11 x 13 x 31 x 41 x 61 x 151 x 331 x 1,321. 18,446,744,073,709,551,608 could have been prime, if it were not for 2,305,843,009,213,693,951 -- a famous Mersenne Prime -- being prime! Unreal. (Or, I should say, logical.)

2,147,483,647 is also a Mersenne Prime. What is happening here? 18,446,744,073,709,551,615 and Mersenne Primes are the 999...999's of binary. There's a pattern between them:

Consider that 1's in binary are 9's in decimal. This pattern is visible in binary (and hexidecimal), and hidden in decimal.

More example prime factorizations below:

 

My Largest Prime:

Letting the loop above run downward, I found my largest prime (ignore claims of larger primes found below in this same document):

18446744073709551557: PRIME

:)

 

One Hundred Billion, Trillion, Ten Trillion, One Hundred Trillion, Etc.:

Here's another example, starting at 100,000,000,000:

100000000000: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.
100000000001: 11, 11, 23, 4093, 8779.
100000000002: 2, 3, 7, 1543, 1543067.
100000000003: PRIME
100000000004: 2, 2, 17573, 1422637.
100000000005: 3, 5, 19, 1627, 215659.
100000000006: 2, 3947, 12667849.
100000000007: 353, 283286119.
100000000008: 2, 2, 2, 3, 3, 3, 462962963.
100000000009: 7, 13, 53, 1979, 10477.
100000000010: 2, 5, 101, 3541, 27961.
100000000011: 3, 37, 37, 24348673.
100000000012: 2, 2, 11, 31, 73313783.
100000000013: 5501, 18178513.
100000000014: 2, 3, 17, 9059, 108223.
100000000015: 5, 79, 253164557.
100000000016: 2, 2, 2, 2, 7, 892857143.
100000000017: 3, 3, 11111111113.
100000000018: 2, 881, 56753689.
100000000019: PRIME
100000000020: 2, 2, 3, 5, 1666666667.
...

And another, starting at 1,000,000,000,000:

1000000000000: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.
1000000000001: 73, 137, 99990001.
1000000000002: 2, 3, 166666666667.
1000000000003: 61, 14221, 1152763.
1000000000004: 2, 2, 17, 149, 197, 501001.
1000000000005: 3, 5, 66666666667.
1000000000006: 2, 7, 607, 117674747.
1000000000007: 34519, 28969553.
1000000000008: 2, 2, 2, 3, 3, 1667, 8331667.
1000000000009: 29, 66413, 519217.
1000000000010: 2, 5, 11, 11, 23, 4093, 8779.
1000000000011: 3, 269, 5107, 242639.
1000000000012: 2, 2, 13, 19, 1012145749.
1000000000013: 7, 142857142859.
1000000000014: 2, 3, 166666666669.
1000000000015: 5, 47, 1171, 3633919.
1000000000016: 2, 2, 2, 2, 13177, 4743113.
1000000000017: 3, 3, 461, 241021933.
1000000000018: 2, 39041, 12807049.
1000000000019: 1601, 2593, 240883.
1000000000020: 2, 2, 3, 5, 7, 1543, 1543067.
...

...starting at 10,000,000,000,000:

10000000000000: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.
10000000000001: 11, 859, 1058313049.
10000000000002: 2, 3, 2221, 2287, 328121.
10000000000003: 13, 29, 547, 48492137.
10000000000004: 2, 2, 7, 357142857143.
10000000000005: 3, 5, 43, 2347, 6605827.
10000000000006: 2, 17, 19, 2447, 6326063.
10000000000007: 167, 619, 6959, 13901.
10000000000008: 2, 2, 2, 3, 3, 23, 6038647343.
10000000000009: 47, 69761, 3049927.
10000000000010: 2, 5, 73, 137, 99990001.
10000000000011: 3, 7, 168037, 2833843.
10000000000012: 2, 2, 11, 157, 2053, 705113.
10000000000013: 83, 151, 797893561.
10000000000014: 2, 3, 1666666666669.
10000000000015: 5, 2000000000003.
10000000000016: 2, 2, 2, 2, 13, 59, 814863103.
10000000000017: 3, 3, 3, 370370370371.
10000000000018: 2, 7, 89, 283, 28359301.
10000000000019: 211, 47393364929.
10000000000020: 2, 2, 3, 5, 166666666667
...

...starting at 100,000,000,000,000:

100000000000000: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.
100000000000001: 29, 101, 281, 121499449.
100000000000002: 2, 3, 89, 251, 746079353.
100000000000003: 19, 31, 613, 276964579.
100000000000004: 2, 2, 13, 41, 46904315197.
100000000000005: 3, 5, 7, 5981, 159234401.
100000000000006: 2, 131, 197, 29363, 65983.
100000000000007: 43, 1103, 2083, 1012201.
100000000000008: 2, 2, 2, 3, 3, 3, 457, 3923, 258233.
100000000000009: 17, 541, 1249, 8705453.
100000000000010: 2, 5, 11, 859, 1058313049.
100000000000011: 3, 23, 37, 67, 584620961.
100000000000012: 2, 2, 7, 3571428571429.
100000000000013: 173, 578034682081.
100000000000014: 2, 3, 3329, 7411, 675551.
100000000000015: 5, 617, 64879, 499621.
100000000000016: 2, 2, 2, 2, 509, 3121, 3934309.
100000000000017: 3, 3, 13, 95003, 8996567.
100000000000018: 2, 193, 259067357513.
100000000000019: 7, 7, 2040816326531.
100000000000020: 2, 2, 3, 5, 2221, 2287, 328121.
...

...starting at 1,000,000,000,000,000:

1000000000000000: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.
1000000000000001: 7, 11, 13, 211, 241, 2161, 9091.
1000000000000002: 2, 3, 166666666666667.
1000000000000003: 14902357, 67103479.
1000000000000004: 2, 2, 648931, 385248971.
1000000000000005: 3, 5, 17, 1873, 41161, 50867.
1000000000000006: 2, 53, 349, 27031410499.
1000000000000007: 47, 59, 360620266859.
1000000000000008: 2, 2, 2, 3, 3, 7, 2381, 833316667.
1000000000000009: 179, 367, 47207, 322459.
1000000000000010: 2, 5, 29, 101, 281, 121499449.
1000000000000011: 3, 19, 61, 176651, 1628093.
1000000000000012: 2, 2, 11, 113, 201126307321.
1000000000000013: 1091, 916590284143.
1000000000000014: 2, 3, 13, 5749, 2230042237.
1000000000000015: 5, 7, 8431, 3388854059.
1000000000000016: 2, 2, 2, 2, 62500000000001.
1000000000000017: 3, 3, 1163, 95538358651.
1000000000000018: 2, 23, 23, 23, 3221, 12758387.
1000000000000019: 1151, 868809730669.
1000000000000020: 2, 2, 3, 5, 89, 251, 746079353.
...

...starting at 10,000,000,000,000,000:

10000000000000000: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.
10000000000000001: 353, 449, 641, 1409, 69857.
10000000000000002: 2, 3, 1292257, 1289733131.
10000000000000003: 7, 1428571428571429.
10000000000000004: 2, 2, 389, 128509, 50010001.
10000000000000005: 3, 5, 127, 138563, 37884167.
10000000000000006: 2, 35855291, 139449433.
10000000000000007: 53, 113, 277, 1117, 5396507.
10000000000000008: 2, 2, 2, 3, 3, 138888888888889.
10000000000000009: 197, 11717, 4332288241.
10000000000000010: 2, 5, 7, 11, 13, 211, 241, 2161, 9091.
10000000000000011: 3, 59, 16993, 3324732251.
10000000000000012: 2, 2, 43, 15277, 3805690573.
10000000000000013: 29, 35111, 9821069927.
10000000000000014: 2, 3, 151, 11037527593819.
10000000000000015: 5, 19, 105263157894737.
10000000000000016: 2, 2, 2, 2, 17, 1185281, 31017713.
10000000000000017: 3, 3, 3, 3, 7, 17636684303351.
10000000000000018: 2, 7643, 654193379563.
10000000000000019: 23, 263, 1653165812531.
10000000000000020: 2, 2, 3, 5, 166666666666667.
...

...starting at 100,000,000,000,000,000:

100000000000000000: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.
100000000000000001: 11, 103, 4013, 21993833369.
100000000000000002: 2, 3, 7, 61, 65701, 594085421.
100000000000000003: PRIME
100000000000000004: 2, 2, 20051, 1246820607451.
100000000000000005: 3, 5, 179, 12713, 2929595521.
100000000000000006: 2, 23, 2297, 252829, 3743297.
100000000000000007: 17, 9920467, 592951213.
100000000000000008: 2, 2, 2, 3, 3, 3, 3, 3, 2309, 22278185023.
100000000000000009: 7, 13, 13, 84530853761623.
100000000000000010: 2, 5, 353, 449, 641, 1409, 69857.
100000000000000011: 3, 37, 773, 2221, 524745797.
100000000000000012: 2, 2, 11, 67, 283, 18899, 6342307.
100000000000000013: PRIME
100000000000000014: 2, 3, 29, 574712643678161.
100000000000000015: 5, 20000000000000003.
100000000000000016: 2, 2, 2, 2, 7, 892857142857143.
100000000000000017: 3, 3, 19, 53, 11033873993159.
100000000000000018: 2, 22237301, 2248474309.
100000000000000019: PRIME
100000000000000020: 2, 2, 3, 5, 1292257, 1289733131.
...

I found 3 primes! At this moment, these are the largest prime numbers I have ever found: 100000000000000003, 100000000000000013, and 100000000000000019.

...starting at 1,000,000,000,000,000,000:

1000000000000000000: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.
1000000000000000001: 101, 9901, 999999000001.
1000000000000000002: 2, 3, 17, 131, 1427, 52445056723.
1000000000000000003: PRIME
1000000000000000004: 2, 2, 1801, 246809, 562425889.
1000000000000000005: 3, 5, 44087, 691381, 2187161.
1000000000000000006: 2, 7, 919, 77724234416291.
1000000000000000007: 1370531, 729644203597.
1000000000000000008: 2, 2, 2, 3, 3, 97, 26209, 32779, 166667.
1000000000000000009: PRIME
1000000000000000010: 2, 5, 11, 103, 4013, 21993833369.
1000000000000000011: 3, 53, 389, 16167887342161.
1000000000000000012: 2, 2, 13, 487, 4623217, 8541289.
1000000000000000013: 7, 6581, 201307, 107832877.
1000000000000000014: 2, 3, 23, 23, 79, 3988099511059.
1000000000000000015: 5, 200000000000000003.
1000000000000000016: 2, 2, 2, 2, 297809, 209866055089.
1000000000000000017: 3, 3, 1077697, 103100510729.
1000000000000000018: 2, 19, 26315789473684211.
1000000000000000019: 17, 6047, 124987, 77829863.
1000000000000000020: 2, 2, 3, 5, 7, 61, 65701, 594085421.

I found 2 primes! At this moment, these are the largest prime numbers I have ever found: 1000000000000000003, and 1000000000000000009.

...starting at 10,000,000,000,000,000,000 -- which is as far as I can go with this, due to the C# ulong data type range limitation of 18,446,744,073,709,551,615, the largest integer data type available in C#:

10000000000000000000: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.
10000000000000000001: 11, 909090909090909091.
10000000000000000002: 2, 3, 23, 643, 60689, 1856948927.
10000000000000000003: 13, 17, 43, 18679, 56335953419.
10000000000000000004: 2, 2, 7, 41, 53, 164354743277891.
10000000000000000005: 3, 5, 261382937, 2550536291.
10000000000000000006: 2, 5000000000000000003.
10000000000000000007: 191, 786407, 66576239711.
10000000000000000008: 2, 2, 2, 3, 3, 29, 1721, 2782842551221.
10000000000000000009: 19, 318007, 1655044667173.
10000000000000000010: 2, 5, 101, 9901, 999999000001.
10000000000000000011: 3, 7, 60139, 7918164189469.
10000000000000000012: 2, 2, 11, 2069, 109846654070917.
10000000000000000013: 31, 109284193, 2951759411.
10000000000000000014: 2, 3, 109, 4457, 3430675314713.
10000000000000000015: 5, 107, 1279, 14614221098551.
10000000000000000016: 2, 2, 2, 2, 13, 54783317, 877583281.
10000000000000000017: 3, 3, 3, 47, 47, 61, 89, 30883085111.
10000000000000000018: 2, 7, 947, 14303, 62627, 842041.
10000000000000000019: 157, 8419, 294793, 25663901.
10000000000000000020: 2, 2, 3, 5, 17, 131, 1427, 52445056723.
...

Letting the previous loop run a bit, I found:

10000000000000000051: PRIME

At the time, it was my largest prime found.

 

Powers of Two:

The powers of two prime factors are pretty basic:

1: ...
2: ...
4: 2, 2.
8: 2, 2, 2.
16: 2, 2, 2, 2.
32: 2, 2, 2, 2, 2.
64: 2, 2, 2, 2, 2, 2.
128: 2, 2, 2, 2, 2, 2, 2.
256: 2, 2, 2, 2, 2, 2, 2, 2.
512: 2, 2, 2, 2, 2, 2, 2, 2, 2.
1024: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
2048: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
4096: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
8192: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
16384: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
32768: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
65536: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
131072: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
262144: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
524288: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
1048576: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
2097152: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
4194304: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
8388608: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
16777216: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
33554432: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
67108864: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
134217728: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
268435456: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
536870912: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
1073741824: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
2147483648: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
4294967296: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
8589934592: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
17179869184: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
34359738368: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
68719476736: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
137438953472: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
274877906944: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
549755813888: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
1099511627776: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
2199023255552: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
4398046511104: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
8796093022208: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
17592186044416: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
35184372088832: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
70368744177664: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
140737488355328: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
281474976710656: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
562949953421312: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
1125899906842624: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
2251799813685248: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
4503599627370496: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
9007199254740992: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
18014398509481984: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
36028797018963968: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
72057594037927936: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
144115188075855872: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
288230376151711744: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
576460752303423488: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
1152921504606846976: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
2305843009213693952: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
4611686018427387904: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
9223372036854775808: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
...

 

All 1's, 2's, 3's, ..., 9's:

1: ...
11: PRIME
111: 3, 37.
1111: 11, 101.
11111: 41, 271.
111111: 3, 7, 11, 13, 37.
1111111: 239, 4649.
11111111: 11, 73, 101, 137.
111111111: 3, 3, 37, 333667.
1111111111: 11, 41, 271, 9091.
11111111111: 21649, 513239.
111111111111: 3, 7, 11, 13, 37, 101, 9901.
1111111111111: 53, 79, 265371653.
11111111111111: 11, 239, 4649, 909091.
111111111111111: 3, 31, 37, 41, 271, 2906161.
1111111111111111: 11, 17, 73, 101, 137, 5882353.
11111111111111111: 2071723, 5363222357.
111111111111111111: 3, 3, 7, 11, 13, 19, 37, 52579, 333667.
1111111111111111111: PRIME
11111111111111111111: 11, 41, 101, 271, 3541, 9091, 27961.
...

2: PRIME
22: 2, 11.
222: 2, 3, 37.
2222: 2, 11, 101.
22222: 2, 41, 271.
222222: 2, 3, 7, 11, 13, 37.
2222222: 2, 239, 4649.
22222222: 2, 11, 73, 101, 137.
222222222: 2, 3, 3, 37, 333667.
2222222222: 2, 11, 41, 271, 9091.
22222222222: 2, 21649, 513239.
222222222222: 2, 3, 7, 11, 13, 37, 101, 9901.
2222222222222: 2, 53, 79, 265371653.
22222222222222: 2, 11, 239, 4649, 909091.
222222222222222: 2, 3, 31, 37, 41, 271, 2906161.
2222222222222222: 2, 11, 17, 73, 101, 137, 5882353.
22222222222222222: 2, 2071723, 5363222357.
222222222222222222: 2, 3, 3, 7, 11, 13, 19, 37, 52579, 333667.
2222222222222222222: 2, 1111111111111111111.
...

3: PRIME
33: 3, 11.
333: 3, 3, 37.
3333: 3, 11, 101.
33333: 3, 41, 271.
333333: 3, 3, 7, 11, 13, 37.
3333333: 3, 239, 4649.
33333333: 3, 11, 73, 101, 137.
333333333: 3, 3, 3, 37, 333667.
3333333333: 3, 11, 41, 271, 9091.
33333333333: 3, 21649, 513239.
333333333333: 3, 3, 7, 11, 13, 37, 101, 9901.
3333333333333: 3, 53, 79, 265371653.
33333333333333: 3, 11, 239, 4649, 909091.
333333333333333: 3, 3, 31, 37, 41, 271, 2906161.
3333333333333333: 3, 11, 17, 73, 101, 137, 5882353.
33333333333333333: 3, 2071723, 5363222357.
333333333333333333: 3, 3, 3, 7, 11, 13, 19, 37, 52579, 333667.
3333333333333333333: 3, 1111111111111111111.
...

4: 2, 2.
44: 2, 2, 11.
444: 2, 2, 3, 37.
4444: 2, 2, 11, 101.
44444: 2, 2, 41, 271.
444444: 2, 2, 3, 7, 11, 13, 37.
4444444: 2, 2, 239, 4649.
44444444: 2, 2, 11, 73, 101, 137.
444444444: 2, 2, 3, 3, 37, 333667.
4444444444: 2, 2, 11, 41, 271, 9091.
44444444444: 2, 2, 21649, 513239.
444444444444: 2, 2, 3, 7, 11, 13, 37, 101, 9901.
4444444444444: 2, 2, 53, 79, 265371653.
44444444444444: 2, 2, 11, 239, 4649, 909091.
444444444444444: 2, 2, 3, 31, 37, 41, 271, 2906161.
4444444444444444: 2, 2, 11, 17, 73, 101, 137, 5882353.
44444444444444444: 2, 2, 2071723, 5363222357.
444444444444444444: 2, 2, 3, 3, 7, 11, 13, 19, 37, 52579, 333667.
4444444444444444444: 2, 2, 1111111111111111111.
...

5: PRIME
55: 5, 11.
555: 3, 5, 37.
5555: 5, 11, 101.
55555: 5, 41, 271.
555555: 3, 5, 7, 11, 13, 37.
5555555: 5, 239, 4649.
55555555: 5, 11, 73, 101, 137.
555555555: 3, 3, 5, 37, 333667.
5555555555: 5, 11, 41, 271, 9091.
55555555555: 5, 21649, 513239.
555555555555: 3, 5, 7, 11, 13, 37, 101, 9901.
5555555555555: 5, 53, 79, 265371653.
55555555555555: 5, 11, 239, 4649, 909091.
555555555555555: 3, 5, 31, 37, 41, 271, 2906161.
5555555555555555: 5, 11, 17, 73, 101, 137, 5882353.
55555555555555555: 5, 2071723, 5363222357.
555555555555555555: 3, 3, 5, 7, 11, 13, 19, 37, 52579, 333667.
5555555555555555555: 5, 1111111111111111111.
...

6: 2, 3.
66: 2, 3, 11.
666: 2, 3, 3, 37.
6666: 2, 3, 11, 101.
66666: 2, 3, 41, 271.
666666: 2, 3, 3, 7, 11, 13, 37.
6666666: 2, 3, 239, 4649.
66666666: 2, 3, 11, 73, 101, 137.
666666666: 2, 3, 3, 3, 37, 333667.
6666666666: 2, 3, 11, 41, 271, 9091.
66666666666: 2, 3, 21649, 513239.
666666666666: 2, 3, 3, 7, 11, 13, 37, 101, 9901.
6666666666666: 2, 3, 53, 79, 265371653.
66666666666666: 2, 3, 11, 239, 4649, 909091.
666666666666666: 2, 3, 3, 31, 37, 41, 271, 2906161.
6666666666666666: 2, 3, 11, 17, 73, 101, 137, 5882353.
66666666666666666: 2, 3, 2071723, 5363222357.
666666666666666666: 2, 3, 3, 3, 7, 11, 13, 19, 37, 52579, 333667.
6666666666666666666: 2, 3, 1111111111111111111.
...

And now the lucky numbers:

7: PRIME
77: 7, 11.
777: 3, 7, 37.
7777: 7, 11, 101.
77777: 7, 41, 271.
777777: 3, 7, 7, 11, 13, 37.
7777777: 7, 239, 4649.
77777777: 7, 11, 73, 101, 137.
777777777: 3, 3, 7, 37, 333667.
7777777777: 7, 11, 41, 271, 9091.
77777777777: 7, 21649, 513239.
777777777777: 3, 7, 7, 11, 13, 37, 101, 9901.
7777777777777: 7, 53, 79, 265371653.
77777777777777: 7, 11, 239, 4649, 909091.
777777777777777: 3, 7, 31, 37, 41, 271, 2906161.
7777777777777777: 7, 11, 17, 73, 101, 137, 5882353.
77777777777777777: 7, 2071723, 5363222357.
777777777777777777: 3, 3, 7, 7, 11, 13, 19, 37, 52579, 333667.
7777777777777777777: 7, 1111111111111111111.
...

8: 2, 2, 2.
88: 2, 2, 2, 11.
888: 2, 2, 2, 3, 37.
8888: 2, 2, 2, 11, 101.
88888: 2, 2, 2, 41, 271.
888888: 2, 2, 2, 3, 7, 11, 13, 37.
8888888: 2, 2, 2, 239, 4649.
88888888: 2, 2, 2, 11, 73, 101, 137.
888888888: 2, 2, 2, 3, 3, 37, 333667.
8888888888: 2, 2, 2, 11, 41, 271, 9091.
88888888888: 2, 2, 2, 21649, 513239.
888888888888: 2, 2, 2, 3, 7, 11, 13, 37, 101, 9901.
8888888888888: 2, 2, 2, 53, 79, 265371653.
88888888888888: 2, 2, 2, 11, 239, 4649, 909091.
888888888888888: 2, 2, 2, 3, 31, 37, 41, 271, 2906161.
8888888888888888: 2, 2, 2, 11, 17, 73, 101, 137, 5882353.
88888888888888888: 2, 2, 2, 2071723, 5363222357.
888888888888888888: 2, 2, 2, 3, 3, 7, 11, 13, 19, 37, 52579, 333667.
8888888888888888888: 2, 2, 2, 1111111111111111111.
...

9: 3, 3.
99: 3, 3, 11.
999: 3, 3, 3, 37.
9999: 3, 3, 11, 101.
99999: 3, 3, 41, 271.
999999: 3, 3, 3, 7, 11, 13, 37.
9999999: 3, 3, 239, 4649.
99999999: 3, 3, 11, 73, 101, 137.
999999999: 3, 3, 3, 3, 37, 333667.
9999999999: 3, 3, 11, 41, 271, 9091.
99999999999: 3, 3, 21649, 513239.
999999999999: 3, 3, 3, 7, 11, 13, 37, 101, 9901.
9999999999999: 3, 3, 53, 79, 265371653.
99999999999999: 3, 3, 11, 239, 4649, 909091.
999999999999999: 3, 3, 3, 31, 37, 41, 271, 2906161.
9999999999999999: 3, 3, 11, 17, 73, 101, 137, 5882353.
99999999999999999: 3, 3, 2071723, 5363222357.
999999999999999999: 3, 3, 3, 3, 7, 11, 13, 19, 37, 52579, 333667.
9999999999999999999: 3, 3, 1111111111111111111*

*At first, I solved this one using the prime factorization server: 9999999999999999999. My program was taking too long to recognize 1111111111111111111 was prime, as I did not do the square root optimization in my loop algorithm (the initial value was limited by its square root, but the factorization of it was not). Interestingly, not sure how the prime factorization server does it in a second. This is fast! Perhaps the primes are prestored lookups.

 

Prime Factorization of First One Million Numbers:

Investigate the results yourself. Here are the prime factorizations of numbers 1..1,000,000:

 

Why One is Not a Prime Number:


1 and Prime Numbers - Numberphile

 

Also See:

Also see our Highly Composite Numbers (Anti-Primes) exploration, and our other prototype work.

 

That is all.

 

 

About the Author: I am Matthew Doucette of Xona Games, an award-winning indie game studio that I founded with my twin brother. We make intensified arcade-style retro games. Our business, our games, our technology, and we as competitive gamers have won prestigious awards and received worldwide press. Our business has won $190,000 in contests. Our games have ranked from #1 in Canada to #1 in Japan, have become #1 best sellers in multiple countries, have won game contests, and have held 3 of the top 5 rated spots in Japan of all Xbox LIVE indie games. Our game engines have been awarded for technical excellence. And we, the developers, have placed #1 in competitive gaming competitions -- relating to the games we make. Read about our story, our awards, our games, and view our blog.

© Xona Games Inc. All Rights Reserved