关于质数的几个重要知识点
查看原帖
关于质数的几个重要知识点
1600214
HY_ACM楼主2025/6/28 16:27

·1不是质数

·2是唯一的偶质数(除2以外的质数都必然是奇数)

·若 2 ~ sqrt(n) 之间没有能够整除 n 的数,则 2 ~ n 之间没有数能整除 n

根据以上性质:
      1.我们可以单独处理 2

      2.筛选质数时我们只需要检测奇数就行

      3.试除法验证“n”是否为质数时,只需试除区间“2 ~ sqrt(n)”

C++代码实现:

	if(…)
	{
		cout << 2 << endl;
		
		return 0;
	}
	
	for(int i = 3;; i += 2)
	{
		bool flag = true;
		for(int j = 3; j*j <= i; j += 2)
		{
			if(i % j == 0)
			{
				flag = false; 
				
				break;
			}
		}
		
		if(flag)
		{
			…… 
		} 
	}
2025/6/28 16:27
加载中...