Comment puis-je améliorer mon programme de nombres premiers avec l'algorithme Sieve of Eratosthenes?

EDIT: j'ai ajouté un troisième moyen d'améliorer l'efficacité
EDIT2: Ajout d'une explication pour laquelle Sieve ne devrait pas être la solution et de certaines relations trigonométriques. De plus, j'ai ajouté une note sur l'historique de la question

Votre problème n'est pas de compter tous les nombres premiers dans une plage donnée, mais seulement ceux qui sont générés par votre fonction.

Par conséquent, je ne pense pas que le tamis d'Eratosthène soit la solution pour cet exercice particulier, pour la raison suivante: n est toujours assez petit alors que k peut être très grand. Si k est très grand, alors l'algorithme de Sieve devrait générer un grand nombre de nombres premiers, pour finalement l'utiliser pour un petit nombre de candidats.

Vous pouvez améliorer l'efficacité de votre programme de trois manières:

• Évitez de calculer sin (.) à chaque fois. Vous pouvez utiliser des relations trigonométriques par exemple. De plus, la première fois que vous calculez ces valeurs, stockez-les dans un tableau et réutilisez ces valeurs. Le calcul de sin () prend beaucoup de temps
• Dans votre test pour vérifier si un nombre est premier, limitez la recherche à sqrt (res) . De plus, envisagez de faire le test avec un j impair uniquement, plus 2
• Si un candidat res est égal au précédent, évitez de refaire le test

Quelques trigonométrie
Si c = cos (0,1) et s = sin (0,1), vous pouvez utiliser les relations:

• sin (0,1 (i + 1)) = s * cos (0,1 * i) + c * sin (0,1 * i))
• cos (0,1 (i + 1)) = c * cos (0,1 * i) - s * sin (0,1 * i))

Si n était grand, il devrait être nécessaire de recalculer régulièrement le sin () par la fonction pour éviter de trop calculer les erreurs d'arrondi. Mais cela ne devrait pas être le cas ici car n est toujours assez petit.

Cependant, comme je l'ai mentionné, il est préférable de n'utiliser que l'astuce de "mémorisation" dans un premier temps et de vérifier si cela suffit.

Une note sur l'historique de cette question et pourquoi cette réponse:

Récemment, ce site a reçu plusieurs questions "comment améliorer mon programme, pour compter le nombre de nombres premiers générés par cette fonction k * sin () ..." A ma connaissance, ces questions étaient tous fermés comme duplicata, sous prétexte que le tamis est la solution et a été expliqué dans une précédente question similaire (mais légèrement différente). Maintenant, la même question est réapparue sous une forme légèrement différente "Comment puis-je insérer l'algorithme Sieve dans ce programme ... (avec k * sin () à nouveau)". Et puis j'ai réalisé que le tamis n'était pas la solution. Ce n'est pas une critique des clôtures précédentes car j'ai fait la même erreur dans la compréhension de la question. Cependant, je pense qu'il est temps de proposer une nouvelle solution, même si elle ne correspond pas parfaitement à la nouvelle question

Lorsque vous utilisez une simple Factorisation de la roue , vous pouvez obtenir une très belle accélération de votre code. La factorisation de roue d'ordre 2 utilise le fait que tous les nombres premiers supérieurs à 3 peuvent être écrits comme 6n + 1 ou 6n + 5 pour naturel n em >. Cela signifie que vous n'avez qu'à faire 2 divisions pour 6 numéros. Ou encore plus, tous les nombres premiers plus grands que 5 peuvent être écrits comme 30n + m , avec m dans {1,7,11,13,17,19, 23,29} . (8 divisions pour 30 nombres).

En utilisant ce principe simple, vous pouvez écrire la fonction suivante pour tester vos nombres premiers (roue {2,3}):

% time echo "6000 100000000" | ./a.out                                                                                                                                                                                                        
12999811
echo "6000 100000000"  0.00s user 0.00s system 51% cpu 0.002 total
./a.out  10.12s user 0.00s system 99% cpu 10.124 total

 % time echo "6000 100000000" | ./a.out 
 12999811
 echo "6000 100000000"  0.00s user 0.00s system 48% cpu 0.002 total
 ./a.out  209.66s user 0.00s system 99% cpu 3:29.70 total

int main() {
  long long k, n;

  while (cin >> k >> n) {
    if (n>1000 && k>1000000000000000000) continue;
    int count = 0;
    for (int i = 1; i <= n; i++) {
      long long res = ((1 + sin(0.1*i)) * k) + 1;
      if (isPrime(res)) { count++; }
    }
    cout << count << endl;
  }
  return 0;
}

bool isPrime(long long num) {
  if (num == 1)     return false;   // 1 is not prime
  if (num  < 4)     return true;    // 2 and 3 are prime
  if (num % 2 == 0) return false;   // divisible by 2
  if (num % 3 == 0) return false;   // divisible by 3
  int w = 5;
  while (w*w <= num) {
      if(num % w     == 0) return false; // not prime
      if(num % (w+2) == 0) return false; // not prime
      w += 6;
  }
  return true;                     // must be prime
}

Vous pouvez améliorer votre vitesse de 10 fois simplement en faisant un meilleur travail avec votre division d'essai. Vous testez tous les nombres entiers de 2 à res au lieu de traiter 2 comme un cas particulier et de tester uniquement les nombres impairs de 3 à la racine carrée de res :

// k <= 10^3, n <= 10^9

int main() {
    unsigned k;
    unsigned long long n;

    while (cin >> k >> n) {

        unsigned count = 0;

        for (unsigned long long i = 1; i <= n; i++) {
            unsigned long long j, res = (1 + sin(0.1 * i)) * k + 1;

            bool is_prime = true;

            if (res <= 2 || res % 2 == 0) {
                is_prime = (res == 2);
            } else {
                for (j = 3; j * j <= res; j += 2) {
                    if (res % j == 0) {
                        is_prime = false;
                        break;
                    }
                }
            }

            if (is_prime) {
                count++;
            }
        }

    cout << count << endl;
    }
}

Bien que k = 500 et n = 500000000 va encore prendre une quarantaine de secondes.