首页 > 代码库 > Fermat’s Chirstmas Theorem (素数打表的)
Fermat’s Chirstmas Theorem (素数打表的)
Fermat’s Chirstmas Theorem
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%lld & %lluDescription
In a letter dated December 25, 1640; the great mathematician Pierre de Fermat wrote to Marin Mersenne that he just proved that an odd prime p is expressible as p = a2 + b2 if and only if p is expressible as p = 4c + 1. As usual, Fermat didn’t include the proof, and as far as we know, never
wrote it down. It wasn’t until 100 years later that no one other than Euler proved this theorem.
Input
Your program will be tested on one or more test cases. Each test case is specified on a separate input line that specifies two integers L, U where L ≤ U < 1, 000, 000
The last line of the input file includes a dummy test case with both L = U = −1.
Output
L U x y
where L and U are as specified in the input. x is the total number of primes within the interval [L, U ] (inclusive,) and y is the total number of primes (also within [L, U ]) that can be expressed as a sum of squares.
Sample Input
10 2011 19100 1000-1 -1
Sample Output
10 20 4 211 19 4 2100 1000 143 69
#include<stdio.h> #include<string.h> #define N 1000005int prime[100005]; int flag[1000005]; int e; void getP() // 素数打表,找出素数存栈 { int i, j; e = 0; memset(flag, 0, sizeof(flag) ); //标记初始化 for ( i=2; i<N; i++) { if ( flag[i]==0 ) { prime[e++] = i; //进栈 } for ( j=0; j<e && i*prime[j]<N; j++ ) { flag[ i * prime[j] ] = 1; } } } int main() { int l,u,x,y; getP(); int i; while(scanf("%d %d",&l,&u)) { if(l==-1 && u==-1) break; x=0; y=0; for( i=0; i<e; i++) { if(prime[i]>=l && prime[i]<=u ) { x++; if(prime[i]%4==1) { y++; } } if(prime[i]>u) break; } if(l<=2 && u>=2) { y++; } printf("%d %d %d %d\n",l, u, x, y ); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。