Un Crible d'Atkin bizarre

Télécharger le projet
Commenter

Description

Ceux qui ont consulté l'article Nombres premiers: Crible d'Atkin, se souviennent peut-être que j'avais exprimé ma déception en ce qui concerne la rapidité de l'algorithme.
Finalement, je me suis décidé à le réétudier, en me basant, comme dans le "crible des multiplications", sur des "prints" intermédiaires.
Reportez-vous à Atkin bizarre pour un développement plus détaillé.
 
 

Impression des valeurs de x et y 'utiles'


Le principe de ma démarche est d'utiliser des "prints" pour mieux cerner et "optimiser" ce que le code fait effectivement.
Par exemple, le print suivant: 
mx=10000
############ Boucle A:
x=1,y=
x=2,y= 1
x=3,y= 2
x=4,y= 1
x=5,y= 2 4
x=6,y= 1 5
x=7,y= 2 4
x=8,y= 1 5 7
x=9,y= 2 4 8
x=10,y= 1 5 7
x=11,y= 2 4 8 10
x=12,y= 1 5 7 11
x=13,y= 2 4 8 10
x=14,y= 1 5 7 11 13
x=15,y= 2 4 8 10 14
x=16,y= 1 5 7 11 13
x=17,y= 2 4 8 10 14 16
x=18,y= 1 5 7 11 13 17
x=19,y= 2 4 8 10 14 16
x=20,y= 1 5 7 11 13 17 19
x=21,y= 2 4 8 10 14 16 20
x=22,y= 1 5 7 11 13 17 19
x=23,y= 2 4 8 10 14 16 20 22
x=24,y= 1 5 7 11 13 17 19 23
x=25,y= 2 4 8 10 14 16 20 22
x=26,y= 1 5 7 11 13 17 19 23 25
x=27,y= 2 4 8 10 14 16 20 22 26
x=28,y= 1 5 7 11 13 17 19 23 25
x=29,y= 2 4 8 10 14 16 20 22 26 28
x=30,y= 1 5 7 11 13 17 19 23 25 29
x=31,y= 2 4 8 10 14 16 20 22 26 28
x=32,y= 1 5 7 11 13 17 19 23 25 29 31
x=33,y= 2 4 8 10 14 16 20 22 26 28 32
x=34,y= 1 5 7 11 13 17 19 23 25 29 31
x=35,y= 2 4 8 10 14 16 20 22 26 28 32 34
x=36,y= 1 5 7 11 13 17 19 23 25 29 31 35
x=37,y= 2 4 8 10 14 16 20 22 26 28 32 34
x=38,y= 1 5 7 11 13 17 19 23 25 29 31 35 37
x=39,y= 2 4 8 10 14 16 20 22 26 28 32 34 38
x=40,y= 1 5 7 11 13 17 19 23 25 29 31 35 37
x=41,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40
x=42,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41
x=43,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40
x=44,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43
x=45,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44
x=46,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43
x=47,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46
x=48,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47
x=49,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46
x=50,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49
x=51,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50
x=52,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49
x=53,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52
x=54,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53
x=55,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52
x=56,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55
x=57,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56
x=58,y= 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55
x=59,y= 22 26 28 32 34 38 40 44 46 50 52 56 58
x=60,y= 29 31 35 37 41 43 47 49 53 55 59
x=61,y= 38 40 44 46 50 52 56 58
x=62,y= 41 43 47 49 53 55 59 61
x=63,y= 44 46 50 52 56 58 62
x=64,y= 49 53 55 59 61
x=65,y= 52 56 58 62 64
x=66,y= 59 61 65
x=67,y= 62 64
x=68,y= 65 67
x=69,y= 68
x=70,y=
x=71,y=
x=72,y=
x=73,y=
x=74,y=
x=75,y=
x=76,y=
x=77,y=
x=78,y=
x=79,y=
x=80,y=
x=81,y=
x=82,y=
x=83,y=
x=84,y=
x=85,y=
x=86,y=
x=87,y=
x=88,y=
x=89,y=
x=90,y=
x=91,y=
x=92,y=
x=93,y=
x=94,y=
x=95,y=
x=96,y=
x=97,y=
x=98,y=
x=99,y=
x=100,y=
############ Boucle B:
x=1,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92 94 98
x=2,y=
x=3,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92 94 98
x=4,y=
x=5,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92 94 98
x=6,y=
x=7,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92 94 98
x=8,y=
x=9,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92 94 98
x=10,y=
x=11,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92 94 98
x=12,y=
x=13,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92 94
x=14,y=
x=15,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92 94
x=16,y=
x=17,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92 94
x=18,y=
x=19,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92 94
x=20,y=
x=21,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88 92
x=22,y=
x=23,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88
x=24,y=
x=25,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88
x=26,y=
x=27,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86 88
x=28,y=
x=29,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82 86
x=30,y=
x=31,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82
x=32,y=
x=33,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76 80 82
x=34,y=
x=35,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76
x=36,y=
x=37,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70 74 76
x=38,y=
x=39,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70
x=40,y=
x=41,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64 68 70
x=42,y=
x=43,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62 64
x=44,y=
x=45,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58 62
x=46,y=
x=47,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52 56 58
x=48,y=
x=49,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 50 52
x=50,y=
x=51,y= 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46
x=52,y=
x=53,y= 2 4 8 10 14 16 20 22 26 28 32 34 38
x=54,y=
x=55,y= 2 4 8 10 14 16 20 22 26 28
x=56,y=
x=57,y= 2 4 8 10 14
x=58,y=
x=59,y=
x=60,y=
x=61,y=
x=62,y=
x=63,y=
x=64,y=
x=65,y=
x=66,y=
x=67,y=
x=68,y=
x=69,y=
x=70,y=
x=71,y=
x=72,y=
x=73,y=
x=74,y=
x=75,y=
x=76,y=
x=77,y=
x=78,y=
x=79,y=
x=80,y=
x=81,y=
x=82,y=
x=83,y=
x=84,y=
x=85,y=
x=86,y=
x=87,y=
x=88,y=
x=89,y=
x=90,y=
x=91,y=
x=92,y=
x=93,y=
x=94,y=
x=95,y=
x=96,y=
x=97,y=
x=98,y=
x=99,y=
x=100,y=
############ Boucle C:
x=1,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
x=2,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
x=3,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97
x=4,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
x=5,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
x=6,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97
x=7,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
x=8,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97
x=9,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97
x=10,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97
x=11,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97
x=12,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97
x=13,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95
x=14,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95
x=15,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95
x=16,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93
x=17,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93
x=18,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91
x=19,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91
x=20,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91
x=21,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89
x=22,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89
x=23,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87
x=24,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85
x=25,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85
x=26,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85
x=27,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83
x=28,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81
x=29,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81
x=30,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79
x=31,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77
x=32,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75
x=33,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73
x=34,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73
x=35,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71
x=36,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67
x=37,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67
x=38,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63
x=39,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61
x=40,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59
x=41,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57
x=42,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53
x=43,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51
x=44,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47
x=45,y= 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43
x=46,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
x=47,y= 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
x=48,y= 1 5 7 11 13 17 19 23 25
x=49,y= 1 3 5 7 9 11 13 15 17 19
x=50,y=
x=51,y=
x=52,y=
x=53,y=
x=54,y=
x=55,y=
x=56,y=
x=57,y=
x=58,y=
x=59,y=
x=60,y=
x=61,y=
x=62,y=
x=63,y=
x=64,y=
x=65,y=
x=66,y=
x=67,y=
x=68,y=
x=69,y=
x=70,y=
x=71,y=
x=72,y=
x=73,y=
x=74,y=
x=75,y=
x=76,y=
x=77,y=
x=78,y=
x=79,y=
x=80,y=
x=81,y=
x=82,y=
x=83,y=
x=84,y=
x=85,y=
x=86,y=
x=87,y=
x=88,y=
x=89,y=
x=90,y=
x=91,y=
x=92,y=
x=93,y=
x=94,y=
x=95,y=
x=96,y=
x=97,y=
x=98,y=
x=99,y=
x=100,y=
nous permet de voir ce qu'on peut éviter et comment simplifier la détermination de y et de n pour inverser l'élément du crible correspondant (sv[n] =! sv[n]).
 
 

AtkinA


Nous partons du code JavaSript suivant correspondant à Atkin2: 
function Atkin2(mx) {
  var i,n,nn,x,y,mr=Math.floor(Math.sqrt(mx));
  var sv=[false,false,true,true]; // for 0,1,2,3
  for (i=4; i<=mx; ++i) sv[i]=false;
  for (x=1; x<=mr; ++x) { // Boucle principale
    var xx=x*x,xx3=xx*3,xx4=xx3+xx;
    for (y=1; y<x; ++y) // Boucle A
      if ((n=xx3-y*y)<=mx && (n%12==11)) sv[n]=!sv[n];
    if (xx3<mx)
      for (y=1; y<=mr; ++y) // Boucle B
        if ((n=xx3+y*y)<=mx && (n%12==7)) sv[n]=!sv[n];
    if (xx4<mx)
      for (y=1; y<=mr; ++y) // Boucle C
        if ((n=xx4+y*y)<=mx && (n%12==1||n%12==5)) sv[n]=!sv[n];
  }
  for (n=5; n<=mr; ++n)
    if (sv[n])
      for (nn=n*n,i=nn; i<=mx; i+=nn) sv[i]=false;
  return sv;
}
que nous traduisons en C pour obtenir une version "classique": 
bool *AtkinA(uint mx) {
  uint i,n,nn,x,y,xx,r=(uint)sqrt((double)mx);
  bool *sv=(bool*)malloc(mx+1);
  sv[0]=sv[1]=false; sv[2]=sv[3]=true; // for 0,1,2,3
  for(i=4; i<=mx; i++) sv[i]=false;
  for(x=1; x<=r; x++) {
    xx=3*x*x;
    for(y=1; y<x; y++) if((n=xx-y*y)<=mx && (n%12==11)) sv[n]=!sv[n];
    if(xx<mx) for(y=1; y<=r; y++) if((n=xx+y*y)<=mx && (n%12==7)) sv[n]=!sv[n];
    xx+=x*x;
    if(xx<mx) for(y=1; y<=r; y++) if((n=xx+y*y)<=mx && (n%12==1||n%12==5)) sv[n]=!sv[n];
  }
  for(n=5; n<=r; ++n) if(sv[n]) for(nn=n*n,i=nn; i<=mx; i+=nn) sv[i]=false;
  return sv;
}
AtkinA: (classique avec bool[])
m=10, n=4, t=0 ms
m=100, n=25, t=0 ms
m=1000, n=168, t=0 ms
m=10000, n=1229, t=0 ms
m=100000, n=9592, t=0 ms
m=1000000, n=78498, t=0 ms
m=10000000, n=664579, t=109 ms
m=100000000, n=5761455, t=1529 ms
m=1000000000, n=50847534, t=17628 ms
 
 

AtkinB


Economisons de la mémoire en utilisant qu'un seul bit par élément du crible. 
#define FlipBit(i) sv[i>>5]^=(1<<(i&31))
#define SetFalse(i) sv[i>>5]&=~(1<<(i&31))

uint *AtkinB(uint mx) { // Atkin
  uint i,k=1+mx/32,n,nn,x,y,xx,r=(uint)sqrt((double)mx);
  uint *sv=(uint*)malloc(k*sizeof(uint)); // (mx+1) bits
  sv[0]=12; // 0:false,1:false,2:true,3:true,4:false,...,31:false
  for(i=1; i<k; i++) sv[i]=0; // >31: false
  for(x=1; x<=r; x++) {
    xx=3*x*x;
    for(y=1; y<x; y++) if((n=xx-y*y)<=mx && (n%12==11)) FlipBit(n);
    if(xx<mx)
    for(y=1; y<=r; y++) if((n=xx+y*y)<=mx && (n%12==7)) FlipBit(n);
    xx+=x*x;
    if(xx<mx)
    for(y=1; y<=r; y++) if((n=xx+y*y)<=mx && (n%12==1||n%12==5)) FlipBit(n);
  }
  for(n=5; n<=r; ++n)
    if(sv[n>>5]&(1<<(n&31))) for(nn=n*n,i=nn; i<=mx; i+=nn) SetFalse(i);
  return sv;
}
AtkinB: (classique avec bit[]/32)
m=10, n=4, t=0 ms
m=100, n=25, t=0 ms
m=1000, n=168, t=0 ms
m=10000, n=1229, t=0 ms
m=100000, n=9592, t=0 ms
m=1000000, n=78498, t=0 ms
m=10000000, n=664579, t=46 ms
m=100000000, n=5761455, t=1154 ms
m=1000000000, n=50847534, t=16318 ms

La mémoire utilisée est divisée par 8, et on gagne même en temps d'exécution !
 
 

AtkinC


Voici maintenant la version bizarre Atkin bizarre.
Bizarre car explicitement, ce code du crible d'Atkin ne comporte ni des testes avec n%12, ni des calcul de la forme n=kx²±y², ni même des variables x ou y !!!
Alors que l'algorithme est pourtant basé sur ces notions. 
bool *AtkinC(uint mx) {
  int e;
  uint g,i,a,d,n,nn;
  bool *sv=new bool[mx+1];
  for(i=0; i<=mx; ++i) sv[i]=false;
  sv[2]=true; sv[3]=true; // for 2 and 3
  for(a=11,d=12,g=24; a<=mx; a+=12,d+=12,g+=36) { // Boucle A
    for(n=a,e=g+24; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
    a+=d;
    for(n=a-12,e=g; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
    for(n=a,e=g+36; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
    a+=2*d;
    for(n=a-24,e=g-12;(e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
    for(n=a,e=g+24; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
    for(n=a+d-12,e=g; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
  }
  for(d=0,a=7; a<=mx; a+=(d+=24)) { // Boucle B
    for(uint n=a,e=-12; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
    for(uint n=a+12,e=12; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
  }
  for(d=4,a=5; a<=mx; a+=(d+=8)) { // Boucle C
    for(n=a,e=0; n<=mx; n+=(e+=8)) sv[n]=!sv[n];
    a+=(d+=8);
    for(n=a,e=0; n<=mx; n+=(e+=8)) sv[n]=!sv[n];
    a+=(d+=8);
    for(n=a,e=-24; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
    for(n=a+24,e=24; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
  }
  uint r=(int)sqrt((double)mx);
  for(n=5; n<=r; ++n)
    if(sv[n]) for(nn=n*n,i=nn; i<=mx; i+=nn) sv[i]=false;
  return sv;
}
AtkinC: (bizarre avec bool[])
m=10, n=4, t=0 ms
m=100, n=25, t=0 ms
m=1000, n=168, t=0 ms
m=10000, n=1229, t=0 ms
m=100000, n=9592, t=0 ms
m=1000000, n=78498, t=0 ms
m=10000000, n=664579, t=31 ms
m=100000000, n=5761455, t=530 ms
m=1000000000, n=50847534, t=8088 ms
 
 

AtkinD


Comme précédemment, économisons la mémoire utilisée: 
#define FlipBit(i) sv[i>>5]^=(1<<(i&31))
#define SetFalse(i) sv[i>>5]&=~(1<<(i&31))

uint *AtkinD(uint mx) {
  int e;
  uint a,d,g,n,k=1+mx/32,r=(uint)sqrt((double)mx);
  uint *sv=(uint*)malloc(k*sizeof(uint)); // (mx+1) bits
  sv[0]=12; // 0:false,1:false,2:true,3:true,4:false,...,31:false
  for(n=1; n<k; ++n) sv[n]=0; // initialize sieve
  for(a=11,d=12,g=24; a<=mx; a+=12,d+=12,g+=36) { // Boucle A
    for(n=a,e=g+24; (e>=48)&&(n<=mx); n+=(e-=72)) FlipBit(n);
    a+=d;
    for(n=a-12,e=g; (e>=48)&&(n<=mx); n+=(e-=72)) FlipBit(n);
    for(n=a,e=g+36; (e>=48)&&(n<=mx); n+=(e-=72)) FlipBit(n);
    a+=2*d;
    for(n=a-24,e=g-12;(e>=48)&&(n<=mx); n+=(e-=72)) FlipBit(n);
    for(n=a,e=g+24; (e>=48)&&(n<=mx); n+=(e-=72)) FlipBit(n);
    for(n=a+d-12,e=g; (e>=48)&&(n<=mx); n+=(e-=72)) FlipBit(n);
  }
  for(d=0,a=7; a<=mx; a+=(d+=24)) { // Boucle B
    for(n=a,e=-12; n<=mx; n+=(e+=72)) FlipBit(n);
    for(n=a+12,e=12; n<=mx; n+=(e+=72)) FlipBit(n);
  }
  for(d=4,a=5; a<=mx; a+=(d+=8)) { // Boucle C
    for(n=a,e=0; n<=mx; n+=(e+=8)) FlipBit(n);
    a+=(d+=8);
    for(n=a,e=0; n<=mx; n+=(e+=8)) FlipBit(n);
    a+=(d+=8);
    for(n=a,e=-24; n<=mx; n+=(e+=72)) FlipBit(n);
    for(n=a+24,e=24; n<=mx; n+=(e+=72)) FlipBit(n);
  }
  for(n=5; n<=r; ++n)
    if(sv[n>>5]&(1<<(n&31))) for(uint nn=n*n,i=nn; i<=mx; i+=nn) SetFalse(i);
  return sv;
}
AtkinD: (bizarre avec bit[]/32)
m=100, n=25, t=0 ms
m=1000, n=168, t=0 ms
m=10000, n=1229, t=0 ms
m=100000, n=9592, t=0 ms
m=1000000, n=78498, t=0 ms
m=10000000, n=664579, t=0 ms
m=100000000, n=5761455, t=359 ms
m=1000000000, n=50847534, t=5397 ms
 
 

AtkinE


Et pour finir, voici une version qui utilise vector<bool>: 
std::vector<bool> AtkinE(uint mx) {
  int e;
  uint a,d,g,n,r=(uint)sqrt((double)mx);
  std::vector<bool> sv(mx+1,false);
  sv[2]=true; sv[3]=true;
  for(a=11,d=12,g=24; a<=mx; a+=12,d+=12,g+=36) { // Boucle A
    for(n=a,e=g+24; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n].flip();
    a+=d;
    for(n=a-12,e=g; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n].flip();
    for(n=a,e=g+36; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n].flip();
    a+=2*d;
    for(n=a-24,e=g-12;(e>=48)&&(n<=mx); n+=(e-=72)) sv[n].flip();
    for(n=a,e=g+24; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n].flip();
    for(n=a+d-12,e=g; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n].flip();
  }
  for(d=0,a=7; a<=mx; a+=(d+=24)) { // Boucle B
    for(n=a,e=-12; n<=mx; n+=(e+=72)) sv[n].flip();
    for(n=a+12,e=12; n<=mx; n+=(e+=72)) sv[n].flip();
  }
  for(d=4,a=5; a<=mx; a+=(d+=8)) { // Boucle C
    for(n=a,e=0; n<=mx; n+=(e+=8)) sv[n].flip();
    a+=(d+=8);
    for(n=a,e=0; n<=mx; n+=(e+=8)) sv[n].flip();
    a+=(d+=8);
    for(n=a,e=-24; n<=mx; n+=(e+=72)) sv[n].flip();
    for(n=a+24,e=24; n<=mx; n+=(e+=72)) sv[n].flip();
  }
  for(n=5; n<=r; ++n)
    if(sv[n]) for(uint nn=n*n,i=nn; i<=mx; i+=nn) sv[i]=false;
  return sv;
}
AtkinE: (bizarre avec vector<bool>)
m=100, n=25, t=0 ms
m=1000, n=168, t=0 ms
m=10000, n=1229, t=0 ms
m=100000, n=9592, t=0 ms
m=1000000, n=78498, t=0 ms
m=10000000, n=664579, t=0 ms
m=100000000, n=5761455, t=422 ms
m=1000000000, n=50847534, t=6302 ms

Une liste actualisée d'articles sur les nombres premiers, complétée de mesures des temps d'exécution, peut être obtenue ici:
Nombres premiers
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (William VOIROL)