nyoj 225 小明求素数积

描述

小明最近遇到了一个素数题，是给你一个正整数N（2=<N<=1000）让你求出2~N的所有素数乘积的后六位。

 

输入

第一行输入一个正整数T(T<=20)表示有T组数据
每组数据占一行，输入一个正整数N（2=<N<=1000）

输出

每组数据输出占一行，输出2~N素数乘积的后六位

样例输入

3
3
6
43

样例输出

6
30
670030

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int mod=1000000;
 8 
 9 int p[1005];
10 int pro[1005];
11 
12 int main()
13 {
14     int T;
15     for(int i=2;i*i<1005;i++)
16         for(int j=i+i;j<1005;j+=i)
17             p[j]=1;
18     memset(pro,1,sizeof(pro));
19     long long tmp=1;;
20     for(int i=2;i<=1000;i++)
21     {
22         if(!p[i])
23             tmp=((tmp%mod)*i)%mod;
24         pro[i]=(int)tmp;
25     }
26     scanf("%d",&T);
27     while(T--)
28     {
29         int n;
30         scanf("%d",&n);
31         printf("%d\n",pro[n]);
32     }
33     return 0;
34 }

 

nyoj 225 小明求素数积

原文：http://www.cnblogs.com/homura/p/4924101.html