Prime Number Challenge

[lars]

So let's open another challenge:
Calculate all prime numbers from 1 to 1000 in the fastest time (not programming time, execution time)

Please post also your device.

I managed it to do it in 3.17 seconds on my iphone 6.

Just to check: here are all prim numbers:

SPOILER: Click to show

1
2
3
5
7
11
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
211
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
421
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
631
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

//Read comment
I will gift the winner with a 5 Euro Steam game, you can select
For christmas



I will run every code 10 times on my device and take the average of it. Please don't copy code from the internet. You need to be able to explain it.

I will post my code later

[lars]

Sorry, I will take back the price.

It was a cool challenge for myself, but I didn't use the internet, and on the internet is some really good code.But I will start a better challenge later, with the same price.

Sorry for that :/
Larce

[warspyking]

This is generally the code I use for something like this:


--Setup
local primes = setmetatable({false},{__index=function(t,k)
     for i = 2, math.sqrt(k) do
        if k%i==0 then
           t[k] = false
           return false
        end
     end
     t[k] = true
     return true
end})

--Usage
for i = 1,2 do
  for ii = 1,1000 do
     print("Loop "..i..": Is "..ii.." prime? "..tostring(primes[ii]))
  end
  print("Press return to run next loop")
  io.read()
end


I make no claims this is fastest at calculating, but the way it works is that once a prime is calculated, it's merely a table lookup, so if you find yourself commonly calculating the same numbers, this is by far the more efficient implementation.

I demonstrate this with 2 iterations, the first one spends time calculating, the second iteration however is nearly immediate. You don't need any amount if tests and averages, it's easy to feel the difference.

[warspyking]

Oh and just a heads up - mathematically speaking, one is not considered a prime number.