C语⾔：素数求解的N种境界
试除法
试除法就是要判断⼀个数x是否为素数，就不断尝试⼩于x⼤于1的⾃然数，只要有⼀个能够整除，则x是合数，否则是素数
1、境界1（最差情况下）
判断x是否为素数，从2⼀直尝试到x-1，这种⽅法效率很差
int main()
{
int i = 0;
int j = 0;
int count = 0;
for (i = 100; i <= 200; ++i)
{
for (j = 2; j < i; ++j)
{
if (i%j == 0)
break;
}
if (j == i)
{
printf("%d是素数\n", i);
count++;
}
}
printf("%d\n", count);
system("pause");
return 0;
}
2、境界2
因为所有素数都是奇数，所以可优化为：
int main()
{
int i = 0;
int j = 0;
int count = 0;
for (i = 101; i <= 200; i += 2)
{
for (j = 2; j < i; ++j)
{
if (i%j == 0)
break;
}
if (j == i)
{
printf("%d是素数\n", i);
count++;
}
}
printf("%d\n", count);
system("pause");
return 0;
}
3、境界3
除了2以外，所有可能的质因数都是奇数，先尝试2，再尝试从3开始直到x/2的所有奇数
int main()
{
int i = 0;
int j = 0;
int count = 0;
for (i = 101; i <= 200; i+=2)
{
for (j = 2; j < i / 2; j++)
{
if (i%j == 0)
break;
}
if (j == i / 2)
{
printf("%d是素数\n", i);
count++;
}
}
printf("%d\n", count);
system("pause");
return 0;
}
4、境界4
只要从2尝试到sqrt(x)就可以，因为因数都是成对出现的，例如100的因数有：1和100、2和50、4和25
、5和20、10和10，成对的因数，其中⼀个必然⼩于等于100的开⽅，另⼀个必然⼤于等于100的开⽅。
int main()
{
int i = 0;
int count = 0;
for (i = 101; i <= 200; i+=2)
{
int j = 0;
for (j = 2; j <= sqrt(i); ++j)
{
if (i%j == 0)
break;
}
if (j>sqrt(i))
{
printf("%d是素数\n", i);
count++;
}
}
printf("%d\n", count);
system("pause");
return 0;
}
5、境界5
只要尝试⼩于sqrt(x)的素数即可，⽽这些素数，在前⾯已经算出，将已经算出的素数，先保存起来，然后⽤于后续的试除，效率⼤⼤提⾼。
筛选法
步骤：
1.先将1去除（1不是素数）
c++判断素数2.⽤2除它后⾯的各个数，把能被2整除的数去除，即把2的倍数去除掉
3.⽤3除后⾯的各个数，把能被3整除的数去除，即把3的倍数去除掉
4.分别⽤5…作为除数除这些数后⾯的数
这些操作需要⼀个很⼤的容器去装载所有数的集合，只要满⾜这些步骤，即将⼤于1的且是2、3、4…的倍数全部置为0，⼀直到数据集合的末尾，最终不是0的数就是素数。
例如：
int main()
{
int i = 9;
int j = 0;
int arr[100];
int count = 0;
for (i = 0; i < 100; ++i)
{
arr[i] = i + 1;
}
for (i = 0; i < 100; ++i)
{
j = i - 1;//空过0、1、2
while (j>1)
{
if (arr[i] % j == 0)
arr[i] = 0;
j = j - 1;
}
}
for (j = 1; j < 100; ++j)
{
if (arr[j] != 0)
{
printf("%d是素数\n", arr[j]);
count++;
}
}
printf("%d\n", count);
system("pause");
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。