315      汽車大全

poj 3006 Dirichlet's Theorem on Arithmetic Progressions 【素數篩】

說實話，題目很長，但是和真正要思考的東西關係不大。。。

就用了之前的素數篩的模板，控製了一下輸入、輸出格式就過了，很水的題，沒什麼技術含量，我好像也隻會用暴搜。。。

#include <stdio.h>

#define MAXN 1000002

int prime[MAXN];		//用篩法求素數，1代表不是素數（被篩掉）

int main()
{
	//先打出素數表
	prime[0]=prime[1]=1;    //開始去掉prime[0]和prime[1]
	int i,j;
	for(i=2;i<MAXN;i++)
	{
		if(prime[i]==0)		//如果prime[i]是素數就把他的倍數都篩掉
		{
			for(j=2*i;j<MAXN;j+=i)
				prime[j]=1;
		}
	}

	int a,d,n;
	int count;
	while(scanf("%d%d%d",&a,&d,&n))
	{
		if(a==0 && d==0 && n==0)
			break;

		count=0;
		for(i=a; ;i+=d)
		{
			if(prime[i]==0)
				count++;

			if(count==n)
				break;
		}

		printf("%d\n",i);
	}

	return 0;
}

最後更新：2017-04-03 14:53:40

  上一篇： clock_gettime測代碼運行時間

  下一篇： JavaScript浮點運算的問題