Ahhh! Another primes problem! I’m starting with the code I used in Problem 7.
After completing Problem 7, I read through some of the forum posts on the problem. I learned two ways to cut the computation time down. First, test only odd numbers. Second, test if each number is prime using all previous primes up to the sqrt of the number.
After running for over 46 minutes, this script resulted in the wrong answer. When taking the sqrt, it allowed perfect squares to slip through into the primes pile.
set primes_sum to 0
set primes_list to {2}
set primes_list_ref to a reference to primes_list
set t to (time of (current date))
log "starting step 1"
repeat with this_num from 2 to 1000000
set this_num to (this_num * 2 - 1)
copy is_this_prime(this_num, primes_list_ref) to this_eval
if this_eval is not {} then
copy this_eval to the end of primes_list_ref
end if
end repeat
to is_this_prime(a_num, primes_list)
set prime_limit to ((the last item of primes_list) ^ 0.5)
repeat with a_prime in primes_list
if a_prime > prime_limit then exit repeat
if (a_num / a_prime mod 1 is 0) then return {}
end repeat
return a_num
end is_this_prime
log "starting step 2"
repeat with n in primes_list
set primes_sum to (primes_sum + n)
end repeat
log ((time of (current date)) - t)
return primes_sum
With this next try, I took the idea of taking out all the evens to the next level. I took out all of the multiples of 2, 3, 5, 7 from even needing to be tested. With a dry run, this change yielded a list of all primes under 10,000 in 2 seconds!
There is definitely a pattern emerging here. I’m contemplating how to integrate this elimination of the small primes into the code, but on a much larger scale. And in a way that generates itself.
I’m still not getting the right answer with this. I’m not sure where to go next so I’m going to move on to the next problem for the time being and come back to this one later with a fresh mind.
set primes_list to {2, 3, 5, 7, 11}
set the_pattern to {13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309}
set the_period to 2310
set bound to (2000000 / the_period)
set primes_list_ref to a reference to primes_list
set t to (time of (current date))
log "starting step 1"
repeat with that_num from 0 to bound
log that_num
repeat with this_pattern in the_pattern
set this_num to (that_num * the_period + this_pattern)
copy is_this_prime(this_num, primes_list_ref) to this_eval
if this_eval is not {} then
copy this_eval to the end of primes_list_ref
end if
end repeat
end repeat
to is_this_prime(a_num, primes_list)
set prime_limit to (((the last item of primes_list) ^ 0.5) + 1)
repeat with a_prime in primes_list
if a_prime > prime_limit then exit repeat
if (a_num / a_prime mod 1 is 0) then return {}
end repeat
return a_num
end is_this_prime
log "starting step 2, " & ((time of (current date)) - t)
set primes_sum to 0
repeat with n in primes_list
if n < 2000000 then
set primes_sum to (primes_sum + n)
end if
end repeat
log primes_list
log ((time of (current date)) - t)
log (count primes_list_ref)
return primes_sum
Now I’m trying Python. So much better! I’ve got some learning to do with this language, but it sure does the trick!
g = []
for n in range(2, 20, 2):
for x in range(2, int(n**.5 + 1)):
if n % x == 0:
break
else:
g.append(n)
print g
sum = sum(g)
print sum