USACO Section 1.5 Superprime Rib

/*
ID: lucien23
PROG: sprime
LANG: C++
*/

#include<iostream>
#include<fstream>
#include<cmath>
#include<set>
using namespace std;
set<int> primes;//10000以内的素数
bool isPrime(int num);
int main()
{
	ifstream infile("sprime.in");
	ofstream outfile("sprime.out");
	if(!infile || !outfile)
	{
		cout<<"file operation failure!"<<endl;
		return -1;
	}

	int N;
	infile>>N;

	//筛选出10000以内的素数
	for (int i=2;i<=10000;i++)
	{
		primes.insert(i);
	}
	for (int i=2;i<=100;i++)
	{
		int num=i*2;
		while(num<=10000)
		{
			primes.erase(num);
			num+=i;
		}
	}

	set<int> sprimes;
	sprimes.insert(2);
	sprimes.insert(3);
	sprimes.insert(5);
	sprimes.insert(7);
	int addition[4]={1,3,7,9};

	for (int i=1;i<N;i++)
	{
		set<int> newSprimes;
		for (set<int>::iterator it=sprimes.begin();it!=sprimes.end();it++)
		{//分别在其后加上1,3,7,9
			for(int j=0;j<4;j++)
			{
				int num=*it*10+addition[j];
				if(isPrime(num))
				{
					newSprimes.insert(num);
				}
			}
		}
		sprimes.clear();
		sprimes=newSprimes;
	}

	for (set<int>::iterator it=sprimes.begin();it!=sprimes.end();it++)
	{
		outfile<<*it<<endl;
	}

	return 0;
}

bool isPrime(int num)
{
	if(num<10000 && primes.find(num)!=primes.end())
		return true;
	int temp=sqrt((double)num);
	for(set<int>::iterator it=primes.begin(); *it<=temp && it!=primes.end(); it++){
		if(num%*it==0)
			return false;
	}
	return true;
}

USACO Section 1.5 Superprime Rib,布布扣,bubuko.com

USACO Section 1.5 Superprime Rib

原文：http://blog.csdn.net/lucienduan/article/details/21482427