我一直在尝试编写一个程序来确定一个数字是否是素数。我的基础是埃拉托色尼筛法。无论如何,我的程序适用于小数字(15485863 有效),但如果我使用大数字(例如 17485863),我会收到分段错误。我正在使用 unsigned long longs 并且不认为我已经超过了它们的最大值。我只是不明白我做错了什么。提前感谢您的任何帮助!
#include <iostream>
#include <limits>
using namespace std;
bool soe (unsigned long long);
int main (void)
{
unsigned long long x = 17485863;
bool q = soe(x);
cout << x << " is ";
if(q)
cout << "prime." << endl;
else
cout << "not prime." << endl;
return 0;
}
bool soe(unsigned long long input)
{
unsigned long long arrayLength = input%2 + input/2;
unsigned long long index = 2;
unsigned long long greatestMult = 0;
bool array[arrayLength];
array[0] = true; //ignore true values in the array
array[1] = true;
do{
array[index] = false;
}while(++index < arrayLength);
index = 2;
do
{
if(input%index != 0)
{
greatestMult = input/index;
while(index*greatestMult > arrayLength)
greatestMult--;
do
{
array[index*greatestMult] = true;
}while(--greatestMult > 0);
do
{
if(!array[index])
break;
}while(++index < arrayLength);
}
else
{
cout << endl << input << " is divisble by " << index << endl;
return false;
}
}while(index < arrayLength);
return true;
}