2 hustis1403 HUSTIS1403 于 2016.02.25 21:42 提问

素数算法 ,为什么num超过int范围就会出错 ,int范围内就没问题,是a*a溢出导致的么

#include
#include
using namespace std;
typedef unsigned long long ULL;
inline bool isPrime(ULL);
inline ULL powMod(ULL a, ULL n, ULL k);
int main()
{
clock_t begin, end;
begin = clock();
ULL num=0;
for (size_t i = 0;i != 500;++i)//素数验证
{
--num;
if (isPrime(num))
cout << num << "是素数" << endl;
}
end = clock();

cout << "运行时间为:" << (double(end - begin) / CLOCKS_PER_SEC) * 1000.0 << "毫秒" << endl;
while (1);
return 0;

}

inline bool isPrime(ULL num)
{
srand((unsigned)time(NULL));
for (size_t i = 0;i != 20;++i)
if (powMod(rand()%32768+1, num - 1, num) != 1)
return false;
return true;
}

inline ULL powMod(ULL a, ULL n, ULL k)//a^n%k
{
if (n == 0)return 1;
ULL ullResult = powMod((a*a) % k, n / 2, k);
if (n % 2)
ullResult = (ullResult*a) % k;
return ullResult;
}

2个回答

devmiao
devmiao   Ds   Rxr 2016.02.25 21:53

size_t不同平台不同,32位下它相当于unsigned int,所以溢出

HUSTIS1403
HUSTIS1403 但是size_t只是用在了循环变量上,没有参与计算啊。。
2 年多之前 回复
li980ex
li980ex   2016.02.26 21:34

num超过int范围,a*a就会溢出,还有检查下是不是除了0

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
唉,栽在了a+b上,注意两个int型相加可能溢出
小明A+B Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 25290    Accepted Submission(s): 12010 Problem Description 小明今年3岁了, 现在他已经能够认识100以
用c++建立一个类PrimeNUM,求指定数据范围内的所有素数(质数)。
具体要求如下: (1)私有数据成员 int data[25]:依次存放在指定范围内求出的所有素数。 int low,high:存放指定的数据范围的下限和上限。 int num:存放low与high之间的素数个数。 (2)公有成员函数 PrimeNUM(int _low,int _high):构造函数,用参数_low和_high初始化low和high,同时初始化num。 int i
建立一个类PrimeNUM,求指定数据范围内的所有素数(质数)。具体要求如下:
建立一个类PrimeNUM,求指定数据范围内的所有素数(质数)。具体要求如下: (1)私有数据成员 int data[25]:依次存放在指定范围内求出的所有素数。 int low,high:存放指定的数据范围的下限和上限。 int num:存放low与high之间的素数个数。 (2)公有成员函数 PrimeNUM(int _low,int _high):构造函数,用参数_low和_hi
输出指定范围内的素数
一、素数,合数       素数又称为质数,是指在大于1的整数中,只能被1和其本身整除的数。      合数:在大于1的整数中不是素数的数。      1既不是素数也不是合数。 二、实现代码     通常用穷举法列出指定范围内的素数。         #include int IsPrime(int n); void PrintPrimes(int,int); int main(
排序(快排,冒泡,堆排,希尔排序)
void doublesort(int a[],int num); void quicksort(int a[],int first,int end); int Partition(int a[],int first, int end); void shellsort(int a[],int num); void creatheap(int a[],int num); void heapsort(int a[],int num);
建立一个类PrimeNUM,求指定数据范围内的所有素数(质数)
1.建立一个类PrimeNUM,求指定数据范围内的所有素数(质数)。具体要求如下:(1)私有数据成员int data[25]:依次存放在指定范围内求出的所有素数。int low,high:存放指定的数据范围的下限和上限。int num:存放low与high之间的素数个数。(2)公有成员函数PrimeNUM(int _low,int _high):构造函数,用参数_low和_high初始化low和h...
Integer 数值范围在-128~127之间时分别使用 ==和 equals进行比较
Integer a=128; Integer b=128; Integer c=127; Integer d=127; System.out.println(a==b);//false System.out.println(a.equals(b));//true System.out.println(a==Integer.valueOf(128));//false System.o
mysql数据库中的自增字段会不会溢出,我用的是int,万一超过这个int的表示范围会怎样
mysql数据库中的自增字段会不会溢出,我用的是int,万一超过这个int的表示范围会怎样 举报描述不清违规检举侵权投诉| 分享| 2015-04-23 11:37 princelions | 浏览 596 次 数据库 可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。 mysql数据库 溢出 int 搜索资料 我有更好的答案
求某个数范围内的素数个数
#include <QCoreApplication> #include <iostream>using namespace std;int main(int argc, char *argv[]) { QCoreApplication a(argc, argv); int range_max;//最大值 cout<<"请输入最大素数检测界限值:"; cin>>ran
一个int溢出的小问题
在进行时间转换时,发现出现了异常,Date begin = new Date(now.getTime()-1000*60*60*24*30);得到的日期竟然比当前日期靠后。后来进行了实验,原来是1000*60*60*24*30溢出了。当int溢出后,又从int的最小值开始网上加,因此变成了负数。 声明long l = 1000*60*60*24*30是没用的,因为等号右边的是in