PDA

View Full Version : I reinvented the finding prime numbers script in python

kielanmatt
July 24th, 2008, 09:20 PM
i learned and re-invented the prime number script before getting to section 4.4 on python.org tutorial i re worked it and i think it works (i tried with the first 100 primes and ok)

This is it

# Finding prime numbers using a computer Erastothenes or summink like that sieve
f = 11 #f will be a very important value
ged = 16 #i can't be bothered to let the computer test 15 lower numbers so i start with 16
print ('2,3,5,7,11,13') # due to the construction of this script the first 6 primes are not
#written
while ged < 5000: #highest number to test
f = 11 #make sure that f equals 11 after the second WHILE statement BREAKS
if ged/2 == (ged-1)/2: # filters out any even numbers
if ged/3 == (ged-1)/3: # clears any multiplies of three
if ged/5 == (ged-1)/5: # any numbers ending with 0 or 5
if ged/7 == (ged-1)/7: # any multiplies of 7, this is done
# so there is less calculations in the loop below
while f <= ged: # there is no point in having the
# divisor "f" higher than the dividend "ged"this loop is not very processor efficient
# because it makes a lot of calculations
if ged/f == (ged-1)/f: # if ged is a
# multiple of f the answear to (ged-1)/f will be lower by 1 and get redirected to f = f+2
if f == ged: # no point to this
# function its here just to get the else function ELSE beneath working
print (ged) # prints ged
ged = ged+1 # makes ged
# higher by 1 so the next number gets tested
break # breaks the loop and
# returns to the first loop
else:
f = f+2 # if f is lower than
# ged AND ged is not the multiple of f, the next line adds 2 to f. This is because there is
# no use in having the divisor an even number, line 6 does the job already
elif f == ged: # does same as IF 5 lines
# above but if i were to delete that one the process would freeze at number 113
print (ged) # prints ged
ged = ged+1 # makes ged higher
break # breaks the loop
else: # if ged/f == (ged-1)/f OR f == ged do
# not apply
ged = ged +1 # makes ged higher
break # breaks the loop
else: # if the number tested "ged" is a multiple of 7
ged = ged+1 # repeat the loop with ged higher by 1
else: # if ged is a multiple of 5
ged = ged+1 # start again with a higher number
else: # if ged is a multiple of 3
ged = ged+1 # start again with ged higher
else: # if ged is a multiple of 2 /even number
ged = ged+1 # start again
#im currently working on a script that tests only one specified number, but i have to get to
#know the INPUT command

Im soo proud i made it (Im 13 ) i know its not a big achievement

ssam
July 24th, 2008, 09:59 PM
An easier way to check if a number is a dividable by another is

if (n%7 == 0):
print n, "divides exactly by 7"

the % operator gives you the remainder. if the remainder is 0 then it divides exactly.

have you checked out the programing forum?
http://ubuntuforums.org/forumdisplay.php?f=39

looks like you'll be a fine hacker one day :-)

klange
July 24th, 2008, 10:52 PM
Honestly, I prefer the much simpler but super-slow brute force method as seen in the following bit of Java:

import cs.*;
public class primeCounter {
public static void main (String[] args) {
int start, end;
if (args.length > 0) // Start at
start = Integer.parseInt(args[0]);
else {
System.out.print("Start: ");
}
if (args.length > 1) // Number to collect
end = Integer.parseInt(args[1]);
else {
System.out.print("End: ");
}
primesBetween(start, end);
System.out.println();
}
public static void primesBetween(int start, int end) {
for (int i=start; i<=end; i++) {
if (isPrime(i))
System.out.println(i);
}
}
public static boolean isPrime(int num) {
for (int i=2;i<=num/2+1;i++) {
if (num % i == 0 && num != 2)
return false;
}
return true;
}
}
Works for everything.

wilsonmuse
July 24th, 2008, 11:43 PM
http://en.wikipedia.org/wiki/Prime_number#Finding_prime_numbers

There is a law: that a number not divisible by a prime less than the square root of itself is prime.

popch
July 25th, 2008, 09:34 AM
Honestly, I prefer the much simpler but super-slow brute force method as seen in the following bit of Java (...)

Works for everything.

Except possibly for employment.

kielanmatt
July 25th, 2008, 10:35 AM
guys i only knew about that greek sieve method i'm not a high school post graduate so i dont know about that square root thing and anyway i have seen one algorithm including that and i didnt wanna copy.

i did this algorithm the first day i started programming in python so dont blame me for not knowing about
% function because i only got to section 4 of the programming tutorial

saulgoode
July 25th, 2008, 11:52 AM
Finding prime numbers is far from being a trivial task and is very important in the field of encryption (which is based upon the product of two extremely large prime numbers).

If you are interested in the subject, I would recommend reading In Code (http://www.amazon.com/Code-Mathematical-Journey-Sarah-Flannery/dp/0761123849) by Sarah Flannery.

klange
July 25th, 2008, 12:05 PM
Except possibly for employment.

Which is why that piece of code will never be put on my resume. Good thing I don't have a job that will ever involve finding prime numbers.

kielanmatt
July 25th, 2008, 12:50 PM
i did it up to million it take summink about 4 seconds to generate 25 primes
where at 17-200 it took a second to generate all of 17-200 primes, but i expected that.
I also made the algorithm 1800% more efficient

kielanmatt
July 25th, 2008, 12:55 PM
here you go

[781229, 781243, 781247, 781271, 781283, 781301, 781307, 781309, 781321, 781327]
[781351, 781357, 781367, 781369, 781387, 781397, 781399, 781409, 781423, 781427, 781433, 781453, 781481, 781483, 781493, 781511, 781513, 781519, 781523, 781531, 781559, 781567, 781589, 781601, 781607]
[781619, 781631, 781633, 781661, 781673, 781681, 781721, 781733, 781741, 781771, 781799, 781801, 781817, 781819, 781853, 781861, 781867, 781883, 781889, 781897, 781919, 781951, 781961, 781967, 781969]
[781973, 781987, 781997, 781999, 782003, 782009, 782011, 782053, 782057, 782071, 782083, 782087, 782107, 782113, 782123, 782129, 782137, 782141, 782147, 782149, 782183, 782189, 782191, 782209, 782219]
[782231, 782251, 782263, 782267, 782297, 782311, 782329, 782339, 782371, 782381, 782387, 782389, 782393, 782429, 782443, 782461, 782473, 782489, 782497, 782501, 782519, 782539, 782581, 782611, 782641]
[782659, 782669, 782671, 782687, 782689, 782707, 782711, 782723, 782777, 782783, 782791, 782839, 782849, 782861, 782891, 782911, 782921, 782941, 782963, 782981, 782983, 782993, 783007, 783011, 783019]
[783023, 783043, 783077, 783089, 783119, 783121, 783131, 783137, 783143, 783149, 783151, 783191, 783193, 783197, 783227, 783247, 783257, 783259, 783269, 783283, 783317, 783323, 783329, 783337, 783359]
[783361, 783373, 783379, 783407, 783413, 783421, 783473, 783487, 783527, 783529, 783533, 783553, 783557, 783569, 783571, 783599, 783613, 783619, 783641, 783647, 783661, 783677, 783689, 783691, 783701]
[783703, 783707, 783719, 783721, 783733, 783737, 783743, 783749, 783763, 783767, 783779, 783781, 783787, 783791, 783793, 783799, 783803, 783829, 783869, 783877, 783931, 783953, 784009, 784039, 784061]
[784081, 784087, 784097, 784103, 784109, 784117, 784129, 784153, 784171, 784181, 784183, 784211, 784213, 784219, 784229, 784243, 784249, 784283, 784307, 784309, 784313, 784321, 784327, 784349, 784351]
[784367, 784373, 784379, 784387, 784409, 784411, 784423, 784447, 784451, 784457, 784463, 784471, 784481, 784489, 784501, 784513, 784541, 784543, 784547, 784561, 784573, 784577, 784583, 784603, 784627]
[784649, 784661, 784687, 784697, 784717, 784723, 784727, 784753, 784789, 784799, 784831, 784837, 784841, 784859, 784867, 784897, 784913, 784919, 784939, 784957, 784961, 784981, 785003, 785017, 785033]
[785053, 785093, 785101, 785107, 785119, 785123, 785129, 785143, 785153, 785159, 785167, 785203, 785207, 785219, 785221, 785227, 785249, 785269, 785287, 785293, 785299, 785303, 785311, 785321, 785329]
[785333, 785341, 785347, 785353, 785357, 785363, 785377, 785413, 785423, 785431, 785459, 785461, 785483, 785501, 785503, 785527, 785537, 785549, 785569, 785573, 785579, 785591, 785597, 785623, 785627]
[785641, 785651, 785671, 785693, 785717, 785731, 785737, 785753, 785773, 785777, 785779, 785801, 785803, 785809, 785839, 785857, 785861, 785879, 785903, 785921, 785923, 785947, 785951, 785963, 786001]
[786013, 786017, 786031, 786047, 786053, 786059, 786061, 786077, 786109, 786127, 786151, 786167, 786173, 786179, 786197, 786211, 786223, 786241, 786251, 786271, 786307, 786311, 786319, 786329, 786337]
[786349, 786371, 786407, 786419, 786431, 786433, 786449, 786469, 786491, 786547, 786551, 786553, 786587, 786589, 786613, 786629, 786659, 786661, 786673, 786691, 786697, 786701, 786703, 786707, 786719]
[786739, 786763, 786803, 786823, 786829, 786833, 786859, 786881, 786887, 786889, 786901, 786931, 786937, 786941, 786949, 786959, 786971, 786979, 786983, 787021, 787043, 787051, 787057, 787067, 787069]
[787079, 787091, 787099, 787123, 787139, 787153, 787181, 787187, 787207, 787217, 787243, 787261, 787277, 787289, 787309, 787331, 787333, 787337, 787357, 787361, 787427, 787429, 787433, 787439, 787447]
[787469, 787477, 787483, 787489, 787513, 787517, 787519, 787529, 787537, 787541, 787547, 787573, 787601, 787609, 787621, 787639, 787649, 787667, 787697, 787711, 787747, 787751, 787757, 787769, 787771]
[787777, 787783, 787793, 787807, 787811, 787817, 787823, 787837, 787879, 787883, 787903, 787907, 787939, 787973, 787981, 787993, 787999, 788009, 788023, 788027, 788033, 788041, 788071, 788077, 788087]
[788089, 788093, 788107, 788129, 788153, 788159, 788167, 788173, 788189, 788209, 788213, 788231, 788261, 788267, 788287, 788309, 788317, 788321, 788351, 788353, 788357, 788363, 788369, 788377, 788383]
[788387, 788393, 788399, 788413, 788419, 788429, 788449, 788467, 788479, 788497, 788521, 788527, 788531, 788537, 788549, 788561, 788563, 788569, 788603, 788621, 788651, 788659, 788677, 788687, 788701]
[788719, 788761, 788779, 788789, 788813, 788819, 788849, 788863, 788867, 788869, 788873, 788891, 788897, 788903, 788927, 788933, 788941, 788947, 788959, 788971, 788993, 788999, 789001, 789017, 789029]
[789031, 789067, 789077, 789091, 789097, 789101, 789109, 789121, 789133, 789137, 789149, 789169, 789181, 789221, 789227, 789251, 789311, 789323, 789331, 789343, 789367, 789377, 789389, 789391, 789407]
[789419, 789443, 789473, 789491, 789493, 789511, 789527, 789533, 789557, 789571, 789577, 789587, 789589, 789611, 789623, 789631, 789653, 789671, 789673, 789683, 789689, 789709, 789713, 789721, 789731]
[789739, 789749, 789793, 789823, 789829, 789847, 789851, 789857, 789883, 789941, 789959, 789961, 789967, 789977, 789979, 790003, 790021, 790033, 790043, 790051, 790057, 790063, 790087, 790093, 790099]
[790121, 790169, 790171, 790189, 790199, 790201, 790219, 790241, 790261, 790271, 790277, 790289, 790291, 790327, 790331, 790333, 790351, 790369, 790379, 790397, 790403, 790417, 790421, 790429, 790451]
[790459, 790481, 790501, 790513, 790519, 790523, 790529, 790547, 790567, 790583, 790589, 790607, 790613, 790633, 790637, 790649, 790651, 790693, 790697, 790703, 790709, 790733, 790739, 790747, 790753]
[790781, 790793, 790817, 790819, 790831, 790843, 790861, 790871, 790879, 790883, 790897, 790927, 790957, 790961, 790967, 790969, 790991, 790997, 791003, 791009, 791017, 791029, 791047, 791053, 791081]
[791093, 791099, 791111, 791117, 791137, 791159, 791191, 791201, 791209, 791227, 791233, 791251, 791257, 791261, 791291, 791309, 791311, 791317, 791321, 791347, 791363, 791377, 791387, 791411, 791419]
[791431, 791443, 791447, 791473, 791489, 791519, 791543, 791561, 791563, 791569, 791573, 791599, 791627, 791629, 791657, 791663, 791677, 791699, 791773, 791783, 791789, 791797, 791801, 791803, 791827]
[791849, 791851, 791887, 791891, 791897, 791899, 791909, 791927, 791929, 791933, 791951, 791969, 791971, 791993, 792023, 792031, 792037, 792041, 792049, 792061, 792067, 792073, 792101, 792107, 792109]
[792119, 792131, 792151, 792163, 792179, 792223, 792227, 792229, 792241, 792247, 792257, 792263, 792277, 792283, 792293, 792299, 792301, 792307, 792317, 792359, 792371, 792377, 792383, 792397, 792413]
[792443, 792461, 792479, 792481, 792487, 792521, 792529, 792551, 792553, 792559, 792563, 792581, 792593, 792601, 792613, 792629, 792637, 792641, 792643, 792647, 792667, 792679, 792689, 792691, 792697]
[792703, 792709, 792713, 792731, 792751, 792769, 792793, 792797, 792821, 792871, 792881, 792893, 792907, 792919, 792929, 792941, 792959, 792973, 792983, 792989, 792991, 793043, 793069, 793099, 793103]
[793123, 793129, 793139, 793159, 793181, 793187, 793189, 793207, 793229, 793253, 793279, 793297, 793301, 793327, 793333, 793337, 793343, 793379, 793399, 793439, 793447, 793453, 793487, 793489, 793493]
[793511, 793517, 793519, 793537, 793547, 793553, 793561, 793591, 793601, 793607, 793621, 793627, 793633, 793669, 793673, 793691, 793699, 793711, 793717, 793721, 793733, 793739, 793757, 793769, 793777]
[793787, 793789, 793813, 793841, 793843, 793853, 793867, 793889, 793901, 793927, 793931, 793939, 793957, 793967, 793979, 793981, 793999, 794009, 794011, 794023, 794033, 794039, 794041, 794063, 794071]
[794077, 794089, 794111, 794113, 794119, 794137, 794141, 794149, 794153, 794161, 794173, 794179, 794191, 794201, 794203, 794207, 794221, 794231, 794239, 794249, 794327, 794341, 794363, 794383, 794389]
[794399, 794407, 794413, 794449, 794471, 794473, 794477, 794483, 794491, 794509, 794531, 794537, 794543, 794551, 794557, 794569, 794579, 794587, 794593, 794641, 794653, 794657, 794659, 794669, 794693]
[794711, 794741, 794743, 794749, 794779, 794831, 794879, 794881, 794887, 794921, 794923, 794953, 794957, 794993, 794999, 795001, 795007, 795023, 795071, 795077, 795079, 795083, 795097, 795101, 795103]
[795121, 795127, 795139, 795149, 795161, 795187, 795203, 795211, 795217, 795233, 795239, 795251, 795253, 795299, 795307, 795323, 795329, 795337, 795343, 795349, 795427, 795449, 795461, 795467, 795479]
[795493, 795503, 795517, 795527, 795533, 795539, 795551, 795581, 795589, 795601, 795643, 795647, 795649, 795653, 795659, 795661, 795667, 795679, 795703, 795709, 795713, 795727, 795737, 795761, 795763]
[795791, 795793, 795797, 795799, 795803, 795827, 795829, 795871, 795877, 795913, 795917, 795931, 795937, 795941, 795943, 795947, 795979, 795983, 795997, 796001, 796009, 796063, 796067, 796091, 796121]
[796139, 796141, 796151, 796171, 796177, 796181, 796189, 796193, 796217, 796247, 796259, 796267, 796291, 796303, 796307, 796337, 796339, 796361, 796363, 796373, 796379, 796387, 796391, 796409, 796447]
[796451, 796459, 796487, 796493, 796517, 796531, 796541, 796553, 796561, 796567, 796571, 796583, 796591, 796619, 796633, 796657, 796673, 796687, 796693, 796699, 796709, 796711, 796751, 796759, 796769]
[796777, 796781, 796799, 796801, 796813, 796819, 796847, 796849, 796853, 796867, 796871, 796877, 796889, 796921, 796931, 796933, 796937, 796951, 796967, 796969, 796981, 797003, 797009, 797021, 797029]
[797033, 797039, 797051, 797053, 797057, 797063, 797077, 797119, 797131, 797143, 797161, 797171, 797201, 797207, 797273, 797281, 797287, 797309, 797311, 797333, 797353, 797359, 797383, 797389, 797399]
[797417, 797429, 797473, 797497, 797507, 797509, 797539, 797549, 797551, 797557, 797561, 797567, 797569, 797579, 797581, 797591, 797593, 797611, 797627, 797633, 797647, 797681, 797689, 797701, 797711]
[797729, 797743, 797747, 797767, 797773, 797813, 797833, 797851, 797869, 797887, 797897, 797911, 797917, 797933, 797947, 797957, 797977, 797987, 798023, 798043, 798059, 798067, 798071, 798079, 798089]
[798097, 798101, 798121, 798131, 798139, 798143, 798151, 798173, 798179, 798191, 798197, 798199, 798221, 798223, 798227, 798251, 798257, 798263, 798271, 798293, 798319, 798331, 798373, 798383, 798397]
[798403, 798409, 798443, 798451, 798461, 798481, 798487, 798503, 798517, 798521, 798527, 798533, 798569, 798599, 798613, 798641, 798647, 798649, 798667, 798691, 798697, 798701, 798713, 798727, 798737]
[798751, 798757, 798773, 798781, 798799, 798823, 798871, 798887, 798911, 798923, 798929, 798937, 798943, 798961, 799003, 799021, 799031, 799061, 799063, 799091, 799093, 799103, 799147, 799151, 799171]
[799217, 799219, 799223, 799259, 799291, 799301, 799303, 799307, 799313, 799333, 799343, 799361, 799363, 799369, 799417, 799427, 799441, 799453, 799471, 799481, 799483, 799489, 799507, 799523, 799529]
[799543, 799553, 799573, 799609, 799613, 799619, 799621, 799633, 799637, 799651, 799657, 799661, 799679, 799723, 799727, 799739, 799741, 799753, 799759, 799789, 799801, 799807, 799817, 799837, 799853]
[799859, 799873, 799891, 799921, 799949, 799961, 799979, 799991, 799993, 799999, 800011, 800029, 800053, 800057, 800077, 800083, 800089, 800113, 800117, 800119, 800123, 800131, 800143, 800159, 800161]
[800171, 800209, 800213, 800221, 800231, 800237, 800243, 800281, 800287, 800291, 800311, 800329, 800333, 800351, 800357, 800399, 800407, 800417, 800419, 800441, 800447, 800473, 800477, 800483, 800497]
[800509, 800519, 800521, 800533, 800537, 800539, 800549, 800557, 800573, 800587, 800593, 800599, 800621, 800623, 800647, 800651, 800659, 800663, 800669, 800677, 800687, 800693, 800707, 800711, 800729]
[800731, 800741, 800743, 800759, 800773, 800783, 800801, 800861, 800873, 800879, 800897, 800903, 800909, 800923, 800953, 800959, 800971, 800977, 800993, 800999, 801001, 801007, 801011, 801019, 801037]
[801061, 801077, 801079, 801103, 801107, 801127, 801137, 801179, 801187, 801197, 801217, 801247, 801277, 801289, 801293, 801301, 801331, 801337, 801341, 801349, 801371, 801379, 801403, 801407, 801419]
[801421, 801461, 801469, 801487, 801503, 801517, 801539, 801551, 801557, 801569, 801571, 801607, 801611, 801617, 801631, 801641, 801677, 801683, 801701, 801707, 801709, 801733, 801761, 801791, 801809]
[801811, 801817, 801833, 801841, 801859, 801883, 801947, 801949, 801959, 801973, 801989, 802007, 802019, 802027, 802031, 802037, 802073, 802103, 802121, 802127, 802129, 802133, 802141, 802147, 802159]
[802163, 802177, 802181, 802183, 802189, 802231, 802253, 802279, 802283, 802297, 802331, 802339, 802357, 802387, 802421, 802441, 802453, 802463, 802471, 802499, 802511, 802523, 802531, 802573, 802583]
[802589, 802597, 802603, 802609, 802643, 802649, 802651, 802661, 802667, 802709, 802721, 802729, 802733, 802751, 802759, 802777, 802783, 802787, 802793, 802799, 802811, 802829, 802831, 802873, 802909]
[802913, 802933, 802951, 802969, 802979, 802987, 803027, 803041, 803053, 803057, 803059, 803087, 803093, 803119, 803141, 803171, 803189, 803207, 803227, 803237, 803251, 803269, 803273, 803287, 803311]
[803323, 803333, 803347, 803359, 803389, 803393, 803399, 803417, 803441, 803443, 803447, 803449, 803461, 803479, 803483, 803497, 803501, 803513, 803519, 803549, 803587, 803591, 803609, 803611, 803623]
[803629, 803651, 803659, 803669, 803687, 803717, 803729, 803731, 803741, 803749, 803813, 803819, 803849, 803857, 803867, 803893, 803897, 803911, 803921, 803927, 803939, 803963, 803977, 803987, 803989]
[804007, 804017, 804031, 804043, 804059, 804073, 804077, 804091, 804107, 804113, 804119, 804127, 804157, 804161, 804179, 804191, 804197, 804203, 804211, 804239, 804259, 804281, 804283, 804313, 804317]
[804329, 804337, 804341, 804367, 804371, 804383, 804409, 804443, 804449, 804473, 804493, 804497, 804511, 804521, 804523, 804541, 804553, 804571, 804577, 804581, 804589, 804607, 804611, 804613, 804619]
[804653, 804689, 804697, 804703, 804709, 804743, 804751, 804757, 804761, 804767, 804803, 804823, 804829, 804833, 804847, 804857, 804877, 804889, 804893, 804901, 804913, 804919, 804929, 804941, 804943]
[804983, 804989, 804997, 805019, 805027, 805031, 805033, 805037, 805061, 805067, 805073, 805081, 805097, 805099, 805109, 805111, 805121, 805153, 805159, 805177, 805187, 805213, 805219, 805223, 805241]
[805249, 805267, 805271, 805279, 805289, 805297, 805309, 805313, 805327, 805331, 805333, 805339, 805369, 805381, 805397, 805403, 805421, 805451, 805463, 805471, 805487, 805499, 805501, 805507, 805517]
[805523, 805531, 805537, 805559, 805573, 805583, 805589, 805633, 805639, 805687, 805703, 805711, 805723, 805729, 805741, 805757, 805789, 805799, 805807, 805811, 805843, 805853, 805859, 805867, 805873]
[805877, 805891, 805901, 805913, 805933, 805967, 805991, 806009, 806011, 806017, 806023, 806027, 806033, 806041, 806051, 806059, 806087, 806107, 806111, 806129, 806137, 806153, 806159, 806177, 806203]
[806213, 806233, 806257, 806261, 806263, 806269, 806291, 806297, 806317, 806329, 806363, 806369, 806371, 806381, 806383, 806389, 806447, 806453, 806467, 806483, 806503, 806513, 806521, 806543, 806549]
[806579, 806581, 806609, 806639, 806657, 806671, 806719, 806737, 806761, 806783, 806789, 806791, 806801, 806807, 806821, 806857, 806893, 806903, 806917, 806929, 806941, 806947, 806951, 806977, 806999]
[807011, 807017, 807071, 807077, 807083, 807089, 807097, 807113, 807119, 807127, 807151, 807181, 807187, 807193, 807197, 807203, 807217, 807221, 807241, 807251, 807259, 807281, 807299, 807337, 807371]
[807379, 807383, 807403, 807407, 807409, 807419, 807427, 807463, 807473, 807479, 807487, 807491, 807493, 807509, 807511, 807523, 807539, 807559, 807571, 807607, 807613, 807629, 807637, 807647, 807689]
[807707, 807731, 807733, 807749, 807757, 807787, 807797, 807809, 807817, 807869, 807871, 807901, 807907, 807923, 807931, 807941, 807943, 807949, 807973, 807997, 808019, 808021, 808039, 808081, 808097]
[808111, 808147, 808153, 808169, 808177, 808187, 808211, 808217, 808229, 808237, 808261, 808267, 808307, 808309, 808343, 808349, 808351, 808361, 808363, 808369, 808373, 808391, 808399, 808417, 808421]
[808439, 808441, 808459, 808481, 808517, 808523, 808553, 808559, 808579, 808589, 808597, 808601, 808603, 808627, 808637, 808651, 808679, 808681, 808693, 808699, 808721, 808733, 808739, 808747, 808751]
[808771, 808777, 808789, 808793, 808837, 808853, 808867, 808919, 808937, 808957, 808961, 808981, 808991, 808993, 809023, 809041, 809051, 809063, 809087, 809093, 809101, 809141, 809143, 809147, 809173]
[809177, 809189, 809201, 809203, 809213, 809231, 809239, 809243, 809261, 809269, 809273, 809297, 809309, 809323, 809339, 809357, 809359, 809377, 809383, 809399, 809401, 809407, 809423, 809437, 809443]
[809447, 809453, 809461, 809491, 809507, 809521, 809527, 809563, 809569, 809579, 809581, 809587, 809603, 809629, 809701, 809707, 809719, 809729, 809737, 809741, 809747, 809749, 809759, 809771, 809779]
[809797, 809801, 809803, 809821, 809827, 809833, 809839, 809843, 809869, 809891, 809903, 809909, 809917, 809929, 809981, 809983, 809993, 810013, 810023, 810049, 810053, 810059, 810071, 810079, 810091]
[810109, 810137, 810149, 810151, 810191, 810193, 810209, 810223, 810239, 810253, 810259, 810269, 810281, 810307, 810319, 810343, 810349, 810353, 810361, 810367, 810377, 810379, 810389, 810391, 810401]
[810409, 810419, 810427, 810437, 810443, 810457, 810473, 810487, 810493, 810503, 810517, 810533, 810539, 810541, 810547, 810553, 810571, 810581, 810583, 810587, 810643, 810653, 810659, 810671, 810697]
[810737, 810757, 810763, 810769, 810791, 810809, 810839, 810853, 810871, 810881, 810893, 810907, 810913, 810923, 810941, 810949, 810961, 810967, 810973, 810989, 811037, 811039, 811067, 811081, 811099]
[811123, 811127, 811147, 811157, 811163, 811171, 811183, 811193, 811199, 811207, 811231, 811241, 811253, 811259, 811273, 811277, 811289, 811297, 811337, 811351, 811379, 811387, 811411, 811429, 811441]
[811457, 811469, 811493, 811501, 811511, 811519, 811523, 811553, 811561, 811583, 811607, 811619, 811627, 811637, 811649, 811651, 811667, 811691, 811697, 811703, 811709, 811729, 811747, 811753, 811757]
[811763, 811771, 811777, 811799, 811819, 811861, 811871, 811879, 811897, 811919, 811931, 811933, 811957, 811961, 811981, 811991, 811997, 812011, 812033, 812047, 812051, 812057, 812081, 812101, 812129]
[812137, 812167, 812173, 812179, 812183, 812191, 812213, 812221, 812233, 812249, 812257, 812267, 812281, 812297, 812299, 812309, 812341, 812347, 812351, 812353, 812359, 812363, 812381, 812387, 812393]
[812401, 812431, 812443, 812467, 812473, 812477, 812491, 812501, 812503, 812519, 812527, 812587, 812597, 812599, 812627, 812633, 812639, 812641, 812671, 812681, 812689, 812699, 812701, 812711, 812717]
[812731, 812759, 812761, 812807, 812849, 812857, 812869, 812921, 812939, 812963, 812969, 813013, 813017, 813023, 813041, 813049, 813061, 813083, 813089, 813091, 813097, 813107, 813121, 813133, 813157]
[813167, 813199, 813203, 813209, 813217, 813221, 813227, 813251, 813269, 813277, 813283, 813287, 813299, 813301, 813311, 813343, 813361, 813367, 813377, 813383, 813401, 813419, 813427, 813443, 813493]
[813499, 813503, 813511, 813529, 813541, 813559, 813577, 813583, 813601, 813613, 813623, 813647, 813677, 813697, 813707, 813721, 813749, 813767, 813797, 813811, 813817, 813829, 813833, 813847, 813863]
[813871, 813893, 813907, 813931, 813961, 813971, 813991, 813997, 814003, 814007, 814013, 814019, 814031, 814043, 814049, 814061, 814063, 814067, 814069, 814081, 814097, 814127, 814129, 814139, 814171]
[814183, 814193, 814199, 814211, 814213, 814237, 814241, 814243, 814279, 814309, 814327, 814337, 814367, 814379, 814381, 814393, 814399, 814403, 814423, 814447, 814469, 814477, 814493, 814501, 814531]
[814537, 814543, 814559, 814577, 814579, 814601, 814603, 814609, 814631, 814633, 814643, 814687, 814699, 814717, 814741, 814747, 814763, 814771, 814783, 814789, 814799, 814823, 814829, 814841, 814859]
[814873, 814883, 814889, 814901, 814903, 814927, 814937, 814939, 814943, 814949, 814991, 815029, 815033, 815047, 815053, 815063, 815123, 815141, 815149, 815159, 815173, 815197, 815209, 815231, 815251]
[815257, 815261, 815273, 815279, 815291, 815317, 815333, 815341, 815351, 815389, 815401, 815411, 815413, 815417, 815431, 815453, 815459, 815471, 815491, 815501, 815519, 815527, 815533, 815539, 815543]
[815569, 815587, 815599, 815621, 815623, 815627, 815653, 815663, 815669, 815671, 815681, 815687, 815693, 815713, 815729, 815809, 815819, 815821, 815831, 815851, 815869, 815891, 815897, 815923, 815933]
[815939, 815953, 815963, 815977, 815989, 816019, 816037, 816043, 816047, 816077, 816091, 816103, 816113, 816121, 816131, 816133, 816157, 816161, 816163, 816169, 816191, 816203, 816209, 816217, 816223]
[816227, 816239, 816251, 816271, 816317, 816329, 816341, 816353, 816367, 816377, 816401, 816427, 816443, 816451, 816469, 816499, 816521, 816539, 816547, 816559, 816581, 816587, 816589, 816593, 816649]
[816653, 816667, 816689, 816691, 816703, 816709, 816743, 816763, 816769, 816779, 816811, 816817, 816821, 816839, 816841, 816847, 816857, 816859, 816869, 816883, 816887, 816899, 816911, 816917, 816919]
[816929, 816941, 816947, 816961, 816971, 817013, 817027, 817039, 817049, 817051, 817073, 817081, 817087, 817093, 817111, 817123, 817127, 817147, 817151, 817153, 817163, 817169, 817183, 817211, 817237]
[817273, 817277, 817279, 817291, 817303, 817319, 817321, 817331, 817337, 817357, 817379, 817403, 817409, 817433, 817457, 817463, 817483, 817519, 817529, 817549, 817561, 817567, 817603, 817637, 817651]
[817669, 817679, 817697, 817709, 817711, 817721, 817723, 817727, 817757, 817769, 817777, 817783, 817787, 817793, 817823, 817837, 817841, 817867, 817871, 817877, 817889, 817891, 817897, 817907, 817913]
[817919, 817933, 817951, 817979, 817987, 818011, 818017, 818021, 818093, 818099, 818101, 818113, 818123, 818143, 818171, 818173, 818189, 818219, 818231, 818239, 818249, 818281, 818287, 818291, 818303]
[818309, 818327, 818339, 818341, 818347, 818353, 818359, 818371, 818383, 818393, 818399, 818413, 818429, 818453, 818473, 818509, 818561, 818569, 818579, 818581, 818603, 818621, 818659, 818683, 818687]
[818689, 818707, 818717, 818723, 818813, 818819, 818821, 818827, 818837, 818887, 818897, 818947, 818959, 818963, 818969, 818977, 818999, 819001, 819017, 819029, 819031, 819037, 819061, 819073, 819083]
[819101, 819131, 819149, 819157, 819167, 819173, 819187, 819229, 819239, 819241, 819251, 819253, 819263, 819271, 819289, 819307, 819311, 819317, 819319, 819367, 819373, 819389, 819391, 819407, 819409]
[819419, 819431, 819437, 819443, 819449, 819457, 819463, 819473, 819487, 819491, 819493, 819499, 819503, 819509, 819523, 819563, 819583, 819593, 819607, 819617, 819619, 819629, 819647, 819653, 819659]
[819673, 819691, 819701, 819719, 819737, 819739, 819761, 819769, 819773, 819781, 819787, 819799, 819811, 819823, 819827, 819829, 819853, 819899, 819911, 819913, 819937, 819943, 819977, 819989, 819991]
[820037, 820051, 820067, 820073, 820093, 820109, 820117, 820129, 820133, 820163, 820177, 820187, 820201, 820213, 820223, 820231, 820241, 820243, 820247, 820271, 820273, 820279, 820319, 820321, 820331]
[820333, 820343, 820349, 820361, 820367, 820399, 820409, 820411, 820427, 820429, 820441, 820459, 820481, 820489, 820537, 820541, 820559, 820577, 820597, 820609, 820619, 820627, 820637, 820643, 820649]
[820657, 820679, 820681, 820691, 820711, 820723, 820733, 820747, 820753, 820759, 820763, 820789, 820793, 820837, 820873, 820891, 820901, 820907, 820909, 820921, 820927, 820957, 820969, 820991, 820997]
[821003, 821027, 821039, 821053, 821057, 821063, 821069, 821081, 821089, 821099, 821101, 821113, 821131, 821143, 821147, 821153, 821167, 821173, 821207, 821209, 821263, 821281, 821291, 821297, 821311]
[821329, 821333, 821377, 821383, 821411, 821441, 821449, 821459, 821461, 821467, 821477, 821479, 821489, 821497, 821507, 821519, 821551, 821573, 821603, 821641, 821647, 821651, 821663, 821677, 821741]
[821747, 821753, 821759, 821771, 821801, 821803, 821809, 821819, 821827, 821833, 821851, 821857, 821861, 821869, 821879, 821897, 821911, 821939, 821941, 821971, 821993, 821999, 822007, 822011, 822013]
[822037, 822049, 822067, 822079, 822113, 822131, 822139, 822161, 822163, 822167, 822169, 822191, 822197, 822221, 822223, 822229, 822233, 822253, 822259, 822277, 822293, 822299, 822313, 822317, 822323]
[822329, 822343, 822347, 822361, 822379, 822383, 822389, 822391, 822407, 822431, 822433, 822517, 822539, 822541, 822551, 822553, 822557, 822571, 822581, 822587, 822589, 822599, 822607, 822611, 822631]
[822667, 822671, 822673, 822683, 822691, 822697, 822713, 822721, 822727, 822739, 822743, 822761, 822763, 822781, 822791, 822793, 822803, 822821, 822823, 822839, 822853, 822881, 822883, 822889, 822893]
[822901, 822907, 822949, 822971, 822973, 822989, 823001, 823003, 823013, 823033, 823051, 823117, 823127, 823129, 823153, 823169, 823177, 823183, 823201, 823219, 823231, 823237, 823241, 823243, 823261]
[823271, 823283, 823309, 823337, 823349, 823351, 823357, 823373, 823399, 823421, 823447, 823451, 823457, 823481, 823483, 823489, 823499, 823519, 823541, 823547, 823553, 823573, 823591, 823601, 823619]
[823621, 823637, 823643, 823651, 823663, 823679, 823703, 823709, 823717, 823721, 823723, 823727, 823729, 823741, 823747, 823759, 823777, 823787, 823789, 823799, 823819, 823829, 823831, 823841, 823843]
[823877, 823903, 823913, 823961, 823967, 823969, 823981, 823993, 823997, 824017, 824029, 824039, 824063, 824069, 824077, 824081, 824099, 824123, 824137, 824147, 824179, 824183, 824189, 824191, 824227]
[824231, 824233, 824269, 824281, 824287, 824339, 824393, 824399, 824401, 824413, 824419, 824437, 824443, 824459, 824477, 824489, 824497, 824501, 824513, 824531, 824539, 824563, 824591, 824609, 824641]