题目
打印100以内的素数
思路1
素数的特点：
- 素数一定是奇数
- 一个数如果是合数，那么它一定能够被2到这个合数的开平方内的某个素数整除（这个特点是提升效率的关键）
- 一个数如果不能被从2到它自身开平方的所有素数整除，那么这个数一定是素数
实施步骤1
- 每求一个素数都把它记录下来；放在一个列表或者数组中；
- 只在奇数中判断是否是素数；
- 只拿求过的素数来进行验证当前奇数是否是素数；
- 只验证到自身开平方；
代码1
有了上面的分析，就可以动手写代码了， 我写了C++版本的和Python的版本的两种，如下：
C++版本：
#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;
int main()
{
int prime[100] = {2, 3};
for(int i=5; i<100; i += 2)
{
int j = -1;
int edge = pow(i, 0.5);
int flag = 0;
while (j < 100)
{
j++;
if (prime[j] == 0)
continue;
if (prime[j] > edge)
{
flag = 1;
break;
}
if (i % prime[j] == 0)
{
flag = 2;
break;
}
}
if (flag == 1)
prime[i] = i;
else
continue;
}
for (int i=0; i<100; i++)
{
if (prime[i] != 0)
cout<<setw(3)<<prime[i];
}
system("pause");
return 0;
}
python版本：
prime = [2, 3]
for i in range(5, 100, 2):
edge = i ** 0.5
for j in prime:
if j > edge:
prime.append(i)
break
if i % j == 0:
break
思路2
在思路1的基础上，我们可以把合数去掉，我们从2到它自身开平方的数的倍数从数组或者列表中去掉，那么剩下的数字一定是素数了。
实施步骤2
- 构造一个列表或者数组存放100个长度，存放的都是1
- 去除列表中的合数（标记为0）
- 打印列表或者数组总标记为1的数字就是素数了。
代码2
C++版本
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int sum=0, a[100]={0};
for (int i=2; i<sqrt(100.0); i++)
{
sum = i;
if (a[sum]==0)
{
while (sum < 100)
{
sum = sum + i;
if (sum<100)a[sum] = 1;
}
}
}
for (int i=2; i<100; i++)
{
if (a[i] == 0)cout<<i<<" ";
}
}
Python版本
lst = [0] * 100
for i in range(2, 11):
su = i
while su < 100:
su += i
try:
lst[su] = 1
except IndexError:
pass
for i in range(2, 100):
if lst[i] == 0:
print(i, end=" ")