天勤OJ 题目1135: 素数
题目描述
输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1。
输入有多组数据。
每组一行，输入n。
输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1。
70
11 31 41 61
/********************************** 日期：2013-2-12* 作者：SJF0115* 题号: 天勤OJ 题目1135: 素数* 来源：http://acmclub.com/problem.php?id=1135* 结果：AC* 来源：2008年北京航空航天大学计算机研究生机试真题* 总结：**********************************/#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>int main(){ int n,i,j; int prime[10001];//素数表 //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin); while(scanf("%d",&n)!=EOF) {//筛法求素数 for(i = 2;i < n;i++){ //偶数不是素数 if(i % 2 == 0){ prime[i] = 0; } //奇数 else{ prime[i] = 1; } } for(i = 3;i < sqrt(n);i++){ //如果当前是素数进行调整 if(prime[i]){ //奇数的倍数不是素数 for(j = i+i;j < n;j += i){ prime[j] = 0; } } }//输出if(n <= 11){printf("-1\n");}else{printf("11");for(i = 12;i < n;i++){if(prime[i] && i%10 == 1){printf(" %d",i);}}printf("\n");} } return 0;}