https://stackoverflow.com/questions/502443
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我目前正在尝试一些问题，只是为了练习我的编程技能。（还没有在学校或其他任何地方自学）我遇到了这个问题，它要求我从给定的 txt 文件中读取数字。这个数字将是N。现在我想找到 N <= 10 000 的第 N 个素数。找到它后，我想将其打印到另一个txt文件中。现在，对于问题的大部分部分，我能够理解并设计出一种获得 N 的方法。问题是我正在使用一个数组来保存以前找到的素数，以便使用它们来检查未来的数字。即使我的数组大小为 100，只要输入整数大约 < 15，程序就会崩溃。
#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;
}
我完全根据我的傻瓜指南和我自己来做这件事，所以请原谅一些代码效率低下和我的算法的一般新手。对于 15 以内的素数，它也能正确显示。
谁能告诉我应该如何改进当前的代码？我正在考虑使用 txt 文件代替数组。那可能吗？任何帮助表示赞赏。
解决方案 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;
}
这是对我原先的代码最后确定的版本基。它完美，如果你想增加素数的范围仅是增加阵列数量。感谢您的帮助=）
其他提示
由于您的问题是关于编程而不是数学，所以我也会尽量保持这样的答案。
第一眼看到你的代码让我想知道你到底在这里做什么......如果您阅读答案，您会意识到其中一些人并没有费心去理解您的代码，而另一些人只是将您的代码转储到调试器中并查看发生了什么。是我们太不耐烦了吗？或者仅仅是因为你的代码对于一个相对简单的问题来说太难理解了？
要改进您的代码，请尝试问自己一些问题：
- 什么是
a,b,c, ， ETC？起一个更有意义的名字不是更好吗？ - 你的算法到底是什么？你能用英语清楚地写下一段关于你正在做的事情（以准确的方式）吗？您能否将该段落修改为一系列步骤，您可以在脑海中对任何输入执行这些步骤并确保其正确？
- 所有步骤都必须吗？我们可以合并甚至消除其中一些吗？
- 有哪些步骤用英语很容易表达，但用 C/C++ 需要 10 多行？
- 您的步骤列表有任何结构吗？循环？大的（可能是重复的）块可以作为带有子步骤的单个步骤吗？
当你完成这些问题后，你可能会得到一个清晰的伪代码来解决问题，这很容易解释和理解。之后，您可以使用 C/C++，或者实际上任何通用语言来实现伪代码。
您可能需要考虑两种测试素数的方法：
- 问题域足够小，只需循环遍历数字直到找到第 N 个素数就可能是可接受的解决方案，并且只需不到几毫秒即可完成。您可以对此方法进行许多简单的优化，例如您只需要测试一次是否可以被 2 整除，然后您只需检查奇数，并且只需检查小于或等于的数字为被测数字的平方根。
- 埃拉托色尼筛法 非常有效且易于实施，并且在数学方面非常简单。
至于为什么你的代码崩溃了，我怀疑更改了读取的行
for( int d=0; d<=b; d++)
到
for( int d=0; d<b; d++)
将解决该问题，因为您正在尝试从数组中可能包含垃圾的潜在未初始化元素中读取。
我没有看过你的代码，但是你的数组必须足够大，以包含您将它存储所有值。当然100是不会够针对此问题最输入。
E.g。此代码..
int someArray[100];
someArray[150] = 10;
写入比阵列（150> 100）大的位置。这被称为一个存储器重写。根据所发生的事情是在内存位置你的程序可能会崩溃，立即后，或者根本就不会。
使用阵列时是某种方式断言在你所写入的元素是数组的范围内的良好的做法。或使用执行该检查的阵列型类。
有关问题的最简单的方法是使用STL的vector类。而必须添加元素（向量::的push_back（）），则可以在以后使用数组运算符接入元件[]。矢量也会给你最好的迭代性能。
下面是添加数字0-100到载体中，然后将它们打印的一些示例代码。注意，在我们使用存储在向量项的计数的第二环路。
#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);
}
我想此刻来提高我的功能编程，所以我只是编写了筛快。我想我会在这里发布。如果你仍然在学习，你会觉得很有趣了。
#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;
}
关于如何提高这任何意见将是对了欢迎。
下面是我的代码。在一个巨大的数字工作时，这是很慢！ 它可以计算所有质数在用户输入的数字！
#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;
}
}
首先，你必须更少的代码（这始终是一件好事！），如果你没有特殊情况下为3,5和7。
另外，还可以防止2的特殊情况下，如果你只是设置NUM并[b] = 2并且仅用于阵列中由东西整除测试。
它看起来像你去围绕主for（）循环，的b增加的值。
然后，这导致在发生碰撞，因为可以访问存储器关闭您数组的末尾：
for (int d = 0; d <= b; d++) {
c = num[d];
我觉得你需要得到更清楚的算法在你的脑袋，然后再次接近代码。
运行通过调试你的代码，我发现它与“if ((a % c) == 0)”浮点异常崩溃。这样做的原因是，你还没有初始化在NUM什么，所以你在做“A％0”。
据我所知，在C / C ++ int是一个16位的类型，因此不能容纳在它百万（上限为2 ^ 16 = 32K）。尝试，并宣布“一个”，只要
我认为C标准说int至少与short一样大并且至多一样大long。
在实践int是4个字节，所以它可以保持-2^31和2^31-1之间的数字。
由于这是用于教学目的，我建议实施埃拉托塞尼的筛。
这也应该是你的兴趣： 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.
谢谢你的建议polythinker =）
由于您将需要为更大的质数的值后问题，我建议你遵循dreeves建议，并做了筛子。这是一个非常有用的箭头，在你的颤动。
