Programme de nombres premiers
https://stackoverflow.com/questions/502443
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'essaie actuellement quelques questions uniquement pour mettre en pratique mes compétences en programmation. (Ne le prenant pas à l'école ou quoi que ce soit, autodidacte) J'ai rencontré ce problème qui m'a obligé à lire un numéro à partir d'un fichier txt donné. Ce nombre serait N. Maintenant, je suppose que je recherche le Nième nombre premier pour N & Lt; = 10 000. Après l'avoir trouvé, je suis censé l'imprimer dans un autre fichier txt. Maintenant, pour la plupart des questions de la question, je suis capable de comprendre et d’élaborer une méthode pour obtenir N. Le problème est que j’utilise un tableau pour enregistrer les nombres premiers précédemment trouvés afin de les utiliser pour vérifier les nombres futurs. Même lorsque mon tableau avait la taille 100, tant que l'entier en entrée était approximativement & Lt; 15, le programme se bloque.
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
int main() {
ifstream trial;
trial.open("C:\\Users\\User\\Documents\\trial.txt");
int prime;
trial >> prime;
ofstream write;
write.open("C:\\Users\\User\\Documents\\answer.txt");
int num[100], b, c, e;
bool check;
b = 0;
switch (prime) {
case 1:
{
write << 2 << endl;
break;
}
case 2:
{
write << 3 << endl;
break;
}
case 3:
{
write << 5 << endl;
break;
}
case 4:
{
write << 7 << endl;
break;
}
default:
{
for (int a = 10; a <= 1000000; a++) {
check = false;
if (((a % 2) != 0) && ((a % 3) != 0) && ((a % 5) != 0) && ((a % 7) != 0)) // first filter
{
for (int d = 0; d <= b; d++) {
c = num[d];
if ((a % c) == 0) {
check = true; // second filter based on previous recorded primes in array
break;
}
}
if (!check) {
e = a;
if (b <= 100) {
num[b] = a;
}
b = b + 1;
}
}
if ((b) == (prime - 4)) {
write << e << endl;
break;
}
}
}
}
trial.close();
write.close();
return 0;
}
Je me suis inspiré entièrement de mon guide pour les nuls et de moi-même, alors je pardonne certaines inefficacités du code et la nouveauté générale de mon algorithme. De plus, il affiche correctement les nombres premiers pour un maximum de 15 personnes.
Quelqu'un pourrait-il me dire comment je devrais améliorer le code actuel? Je pense utiliser un fichier txt à la place du tableau. Est-ce possible? Toute aide est appréciée.
La solution 13
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
int main()
{
ifstream trial;
trial.open("C:\\Users\\User\\Documents\\trial.txt");
int prime, e;
trial>>prime;
ofstream write;
write.open("C:\\Users\\User\\Documents\\answer.txt");
int num[10000], currentPrime, c, primePrint;
bool check;
currentPrime=0;
num[currentPrime] = 2;
currentPrime=1;
for(int currentInt=2; currentInt<=1000000; currentInt++)
{check = false;
for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++)
{ c=num[arrayPrime];
if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
break;}
}
if (!check)
{ e=currentInt;
if( currentInt!= 2 ) {
num[currentPrime]= currentInt;}
currentPrime = currentPrime+1;}
if(currentPrime==prime)
{
write<<e<<endl;
break;}
}
trial.close();
write.close();
return 0;
}
Ceci est la version finalisée de mon code original. Cela fonctionne parfaitement et si vous voulez augmenter la plage de nombres premiers, augmentez simplement le nombre de tableaux. Merci pour l'aide =)
Autres conseils
Puisque votre question concerne la programmation plutôt que les mathématiques, je vais essayer de garder ma réponse de cette façon aussi.
Le premier regard de votre code me fait me demander ce que vous faites ici ... Si vous lisez les réponses, vous vous rendrez compte que certaines d’entre elles ne se sont pas donné la peine de comprendre votre code et d’autres simplement de le vider. à un débogueur et voir ce qui se passe. Est-ce que nous sommes si impatients? Ou est-ce simplement que votre code est trop difficile à comprendre pour un problème relativement facile?
Pour améliorer votre code, essayez de vous poser quelques questions:
- Que sont
a,b,c, etc.? Ne vaudrait-il pas mieux donner des noms plus significatifs? - Quel est exactement votre algorithme? Pouvez-vous écrire un paragraphe clairement rédigé en anglais sur ce que vous faites (de manière exacte)? Pouvez-vous modifier le paragraphe en une série d'étapes que vous pouvez effectuer mentalement pour toute entrée et que vous pouvez être sûr qu'il est correct?
- Toutes les étapes sont-elles nécessaires? Peut-on combiner ou même éliminer certains d'entre eux?
- Quelles sont les étapes faciles à exprimer en anglais mais nécessitant, par exemple, plus de 10 lignes en C / C ++?
- Votre liste d'étapes a-t-elle des structures? Boucles? De gros morceaux (probablement répétés) qui peuvent être mis en une seule étape avec des sous-étapes?
Après avoir parcouru les questions, vous aurez probablement un pseudo-code clairement défini qui résout le problème, qui est facile à expliquer et à comprendre. Après cela, vous pouvez implémenter votre pseudo-code en C / C ++, ou en fait, tout langage à usage général.
Vous pouvez envisager de tester la primalité de deux manières différentes:
- Le domaine du problème est suffisamment petit pour que le simple fait de passer en boucle sur les nombres jusqu'à ce que vous trouviez le Nième nombre premier serait probablement une solution acceptable et ne prendrait que quelques millisecondes. Il existe un certain nombre d’optimisations simples que vous pouvez apporter à cette approche. Par exemple, il vous suffit de vérifier si elle est divisible par 2 une seule fois. à la racine aquare du nombre testé.
- The Sieve of Eratosthenes est très efficace, facile à mettre en œuvre et incroyablement léger. fin des choses.
En ce qui concerne la raison pour laquelle votre code plante, je soupçonne de changer la ligne qui lit
for( int d=0; d<=b; d++)
à
for( int d=0; d<b; d++)
résoudra le problème car vous essayez de lire un élément du tableau potentiellement non initialisé qui contient probablement des ordures.
Je n'ai pas examiné votre code, mais votre tableau doit être suffisamment grand pour contenir toutes les valeurs que vous allez y stocker. 100 ne suffira certainement pas pour la plupart des contributions à ce problème.
E.g. ce code ..
int someArray[100];
someArray[150] = 10;
Écrit dans un emplacement plus grand que le tableau (150 > 100). Ceci est connu comme un écrasement de la mémoire. En fonction de ce qui est arrivé à cet emplacement de mémoire, votre programme peut se bloquer immédiatement, plus tard ou jamais du tout.
Une bonne pratique lors de l’utilisation de tableaux consiste à affirmer en quelque sorte que l’élément sur lequel vous écrivez est dans les limites du tableau. Ou utilisez une classe de type tableau qui effectue cette vérification.
Pour résoudre votre problème, l’approche la plus simple consisterait à utiliser la classe de vecteur STL. Bien que vous deviez ajouter des éléments (vector :: push_back ()), vous pourrez accéder ultérieurement aux éléments à l'aide de l'opérateur de tableau []. Vector vous donnera également la meilleure performance itérative.
Voici un exemple de code permettant d’ajouter les nombres de 0 à 100 à un vecteur, puis de les imprimer. Notez que dans la deuxième boucle, nous utilisons le nombre d'éléments stockés dans le vecteur.
#include <vector> // std::vector
...
const int MAX_ITEMS = 100;
std::vector<int> intVector;
intVector.reserve(MAX_ITEMS); // allocates all memory up-front
// add items
for (int i = 0; i < MAX_ITEMS; i++)
{
intVector.push_back(i); // this is how you add a value to a vector;
}
// print them
for (int i = 0; i < intVector.size(); i++)
{
int elem = intVector[i]; // this access the item at index 'i'
printf("element %d is %d\n", i, elem);
}
J'essaie d'améliorer ma programmation fonctionnelle pour le moment, alors je viens de coder le tamis rapidement. Je pense que je vais le poster ici. Si vous êtes encore en train d'apprendre, cela pourrait aussi vous intéresser.
#include <iostream>
#include <list>
#include <math.h>
#include <functional>
#include <algorithm>
using namespace std;
class is_multiple : public binary_function<int, int, bool>
{
public:
bool operator()(int value, int test) const
{
if(value == test) // do not remove the first value
return false;
else
return (value % test) == 0;
}
};
int main()
{
list<int> numbersToTest;
int input = 500;
// add all numbers to list
for(int x = 1; x < input; x++)
numbersToTest.push_back(x);
// starting at 2 go through the list and remove all multiples until you reach the squareroot
// of the last element in the list
for(list<int>::iterator itr = ++numbersToTest.begin(); *itr < sqrt((float) input); itr++)
{
int tmp = *itr;
numbersToTest.remove_if(bind2nd(is_multiple(), *itr));
itr = find(numbersToTest.begin(), numbersToTest.end(), tmp); //remove_if invalidates iterator
// so find it again. kind of ugly
}
// output primes
for(list<int>::iterator itr = numbersToTest.begin(); itr != --numbersToTest.end(); itr++)
cout << *itr << "\t";
system("PAUSE");
return 0;
}
Tout conseil sur la façon d'améliorer ceci serait le bienvenu.
Voici mon code. Lorsque vous travaillez sur un grand nombre, c'est très lent! Il peut calculer tous les nombres premiers avec le nombre que vous avez entré!
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int main()
{
int m;
int n=0;
char ch;
fstream fp;
cout<<"What prime numbers do you want get within? ";
if((cin>>m)==0)
{
cout<<"Bad input! Please try again!\n";
return 1;
}
if(m<2)
{
cout<<"There are no prime numbers within "<<m<<endl;
return 0;
}
else if(m==2)
{
fp.open("prime.txt",ios::in|ios::out|ios::trunc);//create a file can be writen and read. If the file exist, it will be overwriten.
fp<<"There are only 1 prime number within 2.\n";
fp<<"2\n";
fp.close();
cout<<"Congratulations! It has worked out!\n";
return 0;
}
else
{
int j;
int sq;
fp.open("prime.txt",ios::in|ios::out|ios::trunc);
fp<<"2\t\t";
n++;
for(int i=3;i<=m;i+=2)
{
sq=static_cast<int>(sqrt(i))+1;
fp.seekg(0,ios::beg);
fp>>j;
for(;j<sq;)
{
if(i%j==0)
{
break;
}
else
{
if((fp>>j)==NULL)
{
j=3;
}
}
}
if(j>=sq)
{
fp.seekg(0,ios::end);
fp<<i<<"\t\t";
n++;
if(n%4==0)
fp<<'\n';
}
}
fp.seekg(0,ios::end);
fp<<"\nThere are "<<n<<" prime number within "<<m<<".\n";
fp.close();
cout<<"Congratulations! It has worked out!\n";
return 0;
}
}
D'une part, vous auriez moins de code (ce qui est toujours une bonne chose!) si vous n'aviez pas de cas particulier pour 3, 5 et 7.
De plus, vous pouvez éviter le cas spécial pour 2 si vous définissez simplement num [b] = 2 et ne testez que la divisibilité par les éléments de votre tableau.
Il semble que lorsque vous contournez la boucle principale for (), la valeur de b augmente.
Cela provoque alors un blocage car vous accédez à la mémoire à la fin de votre tableau:
for (int d = 0; d <= b; d++) {
c = num[d];
Je pense que vous devez obtenir un algorithme plus clair dans votre tête, puis vous rapprocher du code.
En exécutant votre code dans un débogueur, j'ai constaté qu'il se bloquait avec une exception de virgule flottante à & "; if ((a % c) == 0) &". La raison en est que vous n’avez rien initialisé numériquement, vous faites donc & "% 0 &";.
D'après ce que je sais, en C / C ++, int est un type 16 bits, vous ne pouvez donc pas en contenir un million (la limite est de 2 ^ 16 = 32k). Essayez de déclarer & Quot; un & Quot; aussi longtemps
Je pense que le standard C dit que int est au moins aussi grand que short et au plus grand que long.
En pratique, -2^31 correspond à 4 octets. Il peut donc contenir des nombres compris entre 2^31-1 et <=>.
Comme il s'agit d'un but pédagogique, je suggérerais de mettre en œuvre le tamis d'Eratosthenes .
Cela devrait également vous intéresser: http://en.wikipedia.org/wiki/ Primality_test
for(int currentInt=2; currentInt<=1000000; currentInt++)
{check = false; // Basically the idea for this for loop is to run checks against integers. This is the main for loop in this program. I re initialize check to false ( check is a bool declared above this. )
for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++) // This for loop is used for checking the currentInt against previously found primes which are stored in the num array.
{ c=num[arrayPrime];
if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
break;} // this is the check. I check the number against every stored value in the num array. If it's divisible by any of them, then bool check is set to true.
if ( currentInt == 2)
{ check = false; } // since i preset num[0] = 2 i make an exception for the number 2.
if (!check)
{
e=a;
if(currentPrime <= 100){
num[currentPrime]= currentInt;} // This if uses check to see if the currentInt is a prime.
currentPrime = currentPrime+1;} // increases the value of currentPrime ( previously b ) by one if !check.
if(currentPrime==prime)
{
write<<e<<endl;
break;} // if currentPrime == prime then write the currentInt into a txt file and break loop, ending the program.
Merci pour le conseil polythinker =)
Etant donné que vous aurez besoin de valeurs de nombres premiers plus importantes pour les questions ultérieures , je vous suggère de suivre les conseils de Dreeves et de faire une passoire. C’est une flèche très utile à avoir dans votre carquois.
