Amélioration du code de filtrage principal - O (n^2) à O (n) et suppression des éléments redondants du tableau

Question

Ce code a créé des itérations à travers les numéros 1-100 et élimine les non-primes, ie les feuilles 2,3,5, .. 97 Cependant, il contient 2 boucles pour l'algorithme de tri et est donc lent. En plus de cela, le nombre "0" reste à l'endroit du nombre éliminé.

Ma question est, comment puis-je mettre ce programme à O (n) performance et comment puis-je copier les nombres premiers dans nums [] à un autre tableau de sorte qu'ils sont en ordre?

#include <stdio.h> 

#define MAX 100 

int main() 
{ 
    int nums[MAX]; 
    int i,j; 

    for (i=0;i<MAX;i++) 
    { 
     nums[i] = i; //Place numbers from 1 to 100 in the array 
    } 

    for (i=0;i<MAX;i++) //Loops through each number in the array 
    { 
     for (j=2;j<=9;j++) 
      /* This loop iterates from 2 to 9 and checks if 
      the current number is divisible by it. If it is, 
      it replaces it with 0.*/ 
     { 
      if (nums[i] == 1 || nums[i] == 4 || nums[i] == 6 || nums[i] == 8 || nums[i] == 9 || nums[i] == 10) 
      /*Excludes non-primes less than 11*/ 
      { 
       nums[i] = 0; 
      } 

      if ((nums[i]%j)==0 && nums[i] > 11) 
      { 

       nums[i] = 0; 
      } 
     } 
    } 

    for (i=0;i<MAX;i++) 
    { 
     printf("%d ", nums[i]); 
    } 
    return 0; 
} 

Merci pour votre aide à l'avance!

Answer 1

Oui, il ya O(N) générateurs de premier ordre là (où N est le nombre de nombres premiers pas la taille de la plage pour ceux-ci s'exécute en temps sub-linéaire). Par exemple Euler formule (de projet Euler 27):

p = n² + n + 41; n={0,1,2,...39} 

Ici comparaison de la production de formule contre les nombres premiers:

Output: 41,43,47,53,...61,...71,......83,...97,................113,....131,............151,............173,................197,........223,....................251,....................281,................313,............347,........................383,....................421,........................461,........................503,................547,........................593,............................641,................................691,........................743,........................797,............................853,................................911,............................971,.........................................1033,.............................................1097,...................................1163,...................................1231,.......................................................1301,...................................1373,........................................1447,.......................................................1523,..................................................1601 
Primes: 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,1009,1013,1019,1021,1031,1033,1039,1049,1051,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,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601 

Comme vous pouvez le voir produit des nombres premiers dans l'ordre, mais pas tous. De tels générateurs sont limités à des plages spécifiques. Il existe également des approches numériques pour générer de telles formules sur des plages spécifiques, mais pour les obtenir est beaucoup plus difficile que O(N). Ce dont vous avez besoin est de faire un polynôme d'approximation qui fonctionnerait sur <1,100> mais qui aurait probablement besoin d'un polynôme de haut degré pour maintenir la précision (ou l'utiliser par morceaux). Donc google ajustement polynomial Mais meilleure option serait PSLQ.

Pour plus d'idées sur la façon d'améliorer votre générateur de premier tamis Jetez un oeil à:

• Prime numbers by Eratosthenes quicker sequential than concurrently?

Answer 2

Je ne sais pas ce que vous comptez faire. Mais si c'est un générateur de premier ordre alors regardez cette condition dans votre code if ((nums[i]%j)==0 && nums[i] > 11)nums[i] = 0. Vous filtrer les non-nombres premiers ici si je ne suis pas wrong.Yea ça va filtrer Bellow 100 correctly.But Qu'en est un nombre multiple de 11 ou 13 ou 121 disons que 169 ceux-ci ne filtrent pas vers le bas étant non-prime. Ensuite, vous devez ajouter plus de numéros dans votre vérificateur. Donc, ce n'est pas un bon filtre du tout.
Lets concevoir un filtre :), vous savez tous les nombres premiers sont nombre impair, sauf 2.

Alors tout d'abord, nous allons filtrer tous les même nombre de nos list.Lets dire que nous avons un tableau de 0 et après nous filtrons quel index restera 0 sont des nombres premiers.

for(int a=4; a<MAX; a+=2)nums[a]=1; 
//remove all even(multiple of 2) number, except 2 

maintenant, nous allons filtrer les chances qui sont multiples de ther bizarres comme 9,15,121 etc. Commençons d'abord num impair et filtrer tous leurs multiples

for(int a=3; a<MAX; a+=2) //all odd num below MAX 
{ 
    for(int b=a*2; b<MAX; b+=a)nums[b]=1; 
    //multiple of a's are a*2,a*2+a,a*2+a+a .... 
} 

Donc, dans cette boucle lorsque nous obtenons un num impair nous filtrons tous ses multiples. Donc, tous les nombres impairs qui n'ont pas filtré sont premiers car ils n'ont pas de diviseur sauf 1 et lui-même.

Maintenant, pour vérifier la boucle de résultat à travers le réseau de nums dont l'indice sont encore 0

for(int a=2;a<MAX; a++)if(!nums[a])printf("%d ", a); 

Ouais vous l'idée que je pense et cette approche appelée sieve of Eratosthenes.

Et vous pouvez optimiser ce que j'ai fait un peu si vous le souhaitez.