#include<iostream>
using namespace std;


//进一步减少判断的范围
//定理: 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d.
//证明: 如果n不是素数, 则由定义n有一个因子d满足1<d<n.
//如果d大于sqrt(n), 则n/d是满足1<n/d<=sqrt(n)的一个因子.
//代码:
bool isPrime(int n)
{
    if(n < 2) return false;
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    for(int i = 3; i*i <= n; i += 2)
        if(n%i == 0) return false;
    return true;
}
//时间复杂度O(sqrt(n)/2), 速度提高O((n-sqrt(n))/2).


int main()
{
	for(int i=0;i<100;i++)
	{
		if(isPrime(i))
		{
			cout<<i<<endl;
		}
	}
	return 0;
}