224:
214:
193:
686:// arbitrary search limit limit ← (999999-1)÷2 // initialize the sieve is_2np1_prime(n) ← true, ∀ n ∈ // eliminate numbers of the form (i+j+2ij) for i in for j in // should this be; ? n ← i+j+2ij if (n ≤ limit): is_2np1_prime(n) ← false // 2n+1 is composite // output the list of primes up to (limit×2+1) print 2 for n in : if is_2np1_prime(n): print 2n+1
81:
53:
22:
91:
159:
67:
612:
The sieve of
Eratosthenes crosses out multiples of remaining primes. Such as stated here multiples of all odd numbers are crossed out. So either the description is incorrect, or the statement of equivalence is. A straightforward optimisation of the SoE is to have the sieve only contain odd numbers.
396:
A informal analysis tells me that this algorithm runs in linear time, since you have to generate a list of Z values, then generate a list of values that are no Z values, then map over that list the 2x + 1 function. I think that SOE runs in O(n), Atkin in O(n/log log n). So, it is my impression that
392:
I don't think that this is any faster than the Sieve of
Eratosthenes, though, I think just about anything is easier to understand than Atkin's. I did some simple tests in C and Haskell, my C version of this ran about 75% as fast as the unoptimized SOE. The haskell version ran half as fast, though I
488:
For the primes up to 1000, only 1269 numbers are checked; for the primes up to a million about 3 million are checked (2992491); for the primes up to a billion, almost 5 billion need to be checked (4719424383). This compares reasonably with the asymptotic formula, within about
613:
That would be an "easy exercise for the reader", not notable or worth a patent. It would be notable if found in the 8th century by a
Chinese scolar. 1934 and India, I doubt, but apparently it is present in the literature and must be included in Knowledge on that account.
641:
n ← 1000000 // limit // initialize the sieve is_prime(2) ← true is_prime(i) ← , ∀ i ∈ for all odd a such that 3 ≤ a and a² ≤ n: if not is_prime(a): continue // only this has changed for all odd b such that a ≤ b and ab ≤ n: is_prime(ab) ← false
512:
This algorithm is asymptotically slower even compared to a classical SOE. Unoptimized version of SOE runs at O(n log log n) whereas this algorithm is O(n log n). The latter can be computed from the following sum (and can be easily formalized):
630:
I don't think it's equivalent to the sieve of eratosthenes (even when the optimization of using only odds is used). Here is what Sieve of
Sundaram looks like (where we loop at a = 2i + 1 and b = 2j + 1 instead of i and j):
397:
this is no better than the SOE, except for possibly conciseness. Even in that regard, SOE is smaller than
Sundaram in Haskell (at least in my implemenation) by about 25 characters (not including whitespace).
634:
n ← 1000000 // limit // initialize the sieve is_prime(2) ← true is_prime(i) ← , ∀ i ∈ for all odd a such that 3 ≤ a and a² ≤ n: for all odd b such that a ≤ b and ab ≤ n: is_prime(ab) ← false
563:
I think the statement that 2 is "the only even prime" (== "the only prime divisible by 2") is a bit of a joke. After all, that's equivalent to stating "17 is the only prime divisible by 17."
280:
485:
so in fact for large bounds it becomes slower than the (optimized version of the) SoE. It's even possible, thanks to the Chen-Qi bounds on harmonic numbers, to give an explicit lower bound.
479:
650:
412:
There are about n/4 rows to check, each of which has n/6 down to 1 column to check. A tedious calculation shows that the number of elements (and thus the time complexity) is
372:
Algorithm just one of this type, it faster than
Eratosphenes & easier than Atkins sieves, notably enough IMO. I'll try to figuire out sources/referencies and add them.
761:
756:
711:
1. It would be better if this article followed the presentation in
Honsberger's book more closely. The idea is explained more clearly there, almost without formulas.
717:
3. Sundaram's algorithm effectively sieves using all odd numbers, not just the primes, so it is definitely slower asymptotically than the odds-only variant of the
692:
I'd like to recommend it be included in the article, subject to any corrections/clarifications anyone wants to make. (Feel free to make changes inline.) -
776:
270:
751:
246:
149:
139:
771:
645:
This also shows that the Sieve of
Sundaram is less efficient than the Sieve of Eratosthenes, and that its complexity is Θ(n log n) (since
766:
617:
570:
544:
523:
660:
501:
347:
Unless you (or someone else) can fix these problems in the article, it will fall short of
Knowledge's standards, and may be deleted.
237:
198:
714:
2. There seems to be a lot of original research in the later parts of this article, with all the homemade computer code and so on.
746:
646:
537:
These two sieves are not equivalent and that should be fixed. What they have in common is that they both sieve primes.
33:
114:
104:
58:
175:
417:
574:
548:
527:
728:
664:
621:
697:
497:
718:
638:
while Sieve of
Eratosthenes (using only odd integers) roughly looks like this (only one line is added):
39:
223:
327:
The description of the algorithm is not clear. What does "Derived sequence consist of primary numbers
656:
598:
566:
540:
519:
66:
363:
Changed. I don't really know who Sundaram is, half an houre googling don't help me to figure out it.
21:
245:
on Knowledge. If you would like to participate, please visit the project page, where you can join
724:
402:
229:
213:
192:
693:
492:
311:
303:
594:
590:
680:
348:
740:
689:
Personally I think it is easier to follow in this form than the textual description.
398:
339:
321:
that you link to is a volleyball player. Is he really the inventor of the algorithm ?
314:. I think the article needs a bit more work. Problems with the current version are:
379:
335:
96:
242:
334:
The article needs to include references to show that (i) the algorithm is not
219:
86:
357:
Thanks for response Basicall article just translated from rusiian Knowledge.
732:
701:
668:
625:
602:
578:
552:
531:
506:
406:
382:
351:
80:
52:
366:
Date is all I got for now, I have not any paper sources so it's all I got.
158:
369:
will try to clarify, with this rough description I've made up a programm.
318:
302:
This article has a number of problems. I have left the following note on
721:(which dates back to the original, as explained at its Knowledge page).
324:
The date "in 40th of XX century" needs to be completed and clarified.
112:-related topics. If you would like to participate, please visit the
651:
1/2 + 1/3 + 1/5 + 1/7 + ... + 1/p grows asymptotically as log log n
109:
15:
393:
think my implementation of the latter is probably lacking.
157:
649:) compared to sieve of eratosthenes' Θ(n log log n) (since
679:
I've written some pseudocode for the algorithm, based on
647:
1/2 + 1/3 + 1/4 + ... + 1/n grows asymptotically as log n
378:
I'll appreciate any suggestions about improoving it more
420:
241:, a collaborative effort to improve the coverage of
473:
108:, which aims to improve Knowledge's coverage of
310:I see that you recently created a new article,
8:
474:{\displaystyle ^{1}/_{4}\ n\ln n+\Theta (n)}
683:, and submit it to the public domain here:
187:
47:
436:
431:
424:
419:
762:Knowledge requested photographs in India
757:C-Class India articles of Mid-importance
516:sum_{j = 1}^{n/3} \frac{n - j}{1 + 2j}
189:
49:
19:
7:
235:This article is within the scope of
102:This article is within the scope of
38:It is of interest to the following
459:
14:
777:Mid-priority mathematics articles
255:Knowledge:WikiProject Mathematics
258:Template:WikiProject Mathematics
222:
212:
191:
166:An editor has requested that an
89:
79:
65:
51:
20:
304:the original author's talk page
275:This article has been rated as
144:This article has been rated as
468:
462:
1:
752:Mid-importance India articles
407:09:12, 17 December 2007 (UTC)
249:and see a list of open tasks.
772:C-Class mathematics articles
626:02:06, 4 November 2010 (UTC)
507:20:23, 31 October 2008 (UTC)
383:19:35, 3 December 2007 (UTC)
352:11:14, 3 December 2007 (UTC)
702:02:16, 28 August 2012 (UTC)
675:Pseudocode of the algorithm
608:Equivalent to Eratosthenes?
553:23:08, 3 October 2011 (UTC)
532:23:06, 3 October 2011 (UTC)
124:Knowledge:WikiProject India
793:
767:WikiProject India articles
733:06:14, 6 August 2021 (UTC)
603:02:43, 16 March 2009 (UTC)
338:and (ii) the algorithm is
150:project's importance scale
127:Template:WikiProject India
681:Sieve of Atkin#Pseudocode
669:19:36, 13 June 2012 (UTC)
589:FYI this just came out:
579:07:58, 1 March 2009 (UTC)
274:
207:
165:
143:
74:
46:
281:project's priority scale
238:WikiProject Mathematics
747:C-Class India articles
707:Suggested improvements
475:
162:
28:This article is rated
719:sieve of Eratosthenes
616:Albert van der Horst
585:recent online article
476:
161:
418:
261:mathematics articles
559:Odd vs. Even Primes
471:
230:Mathematics portal
163:
34:content assessment
659:comment added by
569:comment added by
543:comment added by
522:comment added by
505:
443:
336:original research
312:Sieve of Sundaram
295:
294:
291:
290:
287:
286:
186:
185:
182:
181:
105:WikiProject India
784:
671:
591:Sundaram's Sieve
581:
555:
534:
495:
480:
478:
477:
472:
442:
441:
440:
435:
429:
428:
263:
262:
259:
256:
253:
232:
227:
226:
216:
209:
208:
203:
195:
188:
178:to this article.
132:
131:
128:
125:
122:
99:
94:
93:
92:
83:
76:
75:
70:
69:
68:
63:
55:
48:
31:
25:
24:
16:
792:
791:
787:
786:
785:
783:
782:
781:
737:
736:
709:
687:
677:
654:
643:
636:
610:
587:
564:
561:
538:
517:
430:
421:
416:
415:
390:
300:
260:
257:
254:
251:
250:
228:
221:
201:
129:
126:
123:
120:
119:
95:
90:
88:
64:
61:
32:on Knowledge's
29:
12:
11:
5:
790:
788:
780:
779:
774:
769:
764:
759:
754:
749:
739:
738:
708:
705:
685:
676:
673:
640:
633:
609:
606:
586:
583:
560:
557:
510:
509:
490:
486:
483:
482:
481:
470:
467:
464:
461:
458:
455:
452:
449:
446:
439:
434:
427:
423:
389:
386:
376:
375:
374:
373:
370:
367:
364:
355:
354:
345:
344:
343:
332:
325:
322:
299:
296:
293:
292:
289:
288:
285:
284:
273:
267:
266:
264:
247:the discussion
234:
233:
217:
205:
204:
196:
184:
183:
180:
179:
164:
154:
153:
146:Mid-importance
142:
136:
135:
133:
130:India articles
101:
100:
84:
72:
71:
62:Mid‑importance
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
789:
778:
775:
773:
770:
768:
765:
763:
760:
758:
755:
753:
750:
748:
745:
744:
742:
735:
734:
730:
726:
725:Ebony Jackson
722:
720:
715:
712:
706:
704:
703:
699:
695:
690:
684:
682:
674:
672:
670:
666:
662:
658:
652:
648:
639:
632:
628:
627:
623:
619:
618:80.100.243.19
614:
607:
605:
604:
600:
596:
592:
584:
582:
580:
576:
572:
571:77.176.69.185
568:
558:
556:
554:
550:
546:
545:31.175.84.145
542:
535:
533:
529:
525:
524:31.175.84.145
521:
514:
508:
503:
499:
494:
491:
487:
484:
465:
456:
453:
450:
447:
444:
437:
432:
425:
422:
414:
413:
411:
410:
409:
408:
404:
400:
394:
387:
385:
384:
381:
371:
368:
365:
362:
361:
360:
359:
358:
353:
350:
346:
341:
337:
333:
330:
326:
323:
320:
316:
315:
313:
309:
308:
307:
305:
297:
282:
278:
272:
269:
268:
265:
248:
244:
240:
239:
231:
225:
220:
218:
215:
211:
210:
206:
200:
197:
194:
190:
177:
173:
169:
160:
156:
155:
151:
147:
141:
138:
137:
134:
117:
116:
111:
107:
106:
98:
87:
85:
82:
78:
77:
73:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
723:
716:
713:
710:
694:CountingPine
691:
688:
678:
661:27.108.41.75
655:— Preceding
644:
637:
629:
615:
611:
588:
562:
539:— Preceding
536:
518:— Preceding
515:
511:
493:CRGreathouse
395:
391:
377:
356:
328:
301:
277:Mid-priority
276:
236:
202:Mid‑priority
171:
167:
145:
115:project page
113:
103:
97:India portal
40:WikiProjects
565:—Preceding
252:Mathematics
243:mathematics
199:Mathematics
741:Categories
595:Billymac00
172:photograph
349:Gandalf61
657:unsigned
567:unsigned
541:unsigned
520:unsigned
399:Jfredett
331:" mean ?
319:Sundaram
298:Comments
380:Any_Key
340:notable
279:on the
148:on the
30:C-class
36:scale.
388:Speed
176:added
168:image
121:India
110:India
59:India
729:talk
698:talk
665:talk
653:).
622:talk
599:talk
575:talk
549:talk
528:talk
489:10%.
403:talk
317:The
271:Mid
174:be
170:or
140:Mid
743::
731:)
700:)
667:)
624:)
601:)
593:--
577:)
551:)
530:)
500:|
460:Θ
451:
448:ln
405:)
306::
727:(
696:(
663:(
620:(
597:(
573:(
547:(
526:(
504:)
502:c
498:t
496:(
469:)
466:n
463:(
457:+
454:n
445:n
438:4
433:/
426:1
401:(
342:.
329:p
283:.
152:.
118:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
