MyException - 我的异常网
当前位置:我的异常网» 编程 » 天勤OJ 标题1135: 素数

天勤OJ 标题1135: 素数

www.MyException.Cn  网友分享于:2013-02-20  浏览:3次
天勤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,flag,index;
	int prime[10001];//素数表
	//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);
	while(scanf("%d",&n) != EOF)
	{
		index = 0;
		for(i = 11;i < n;i += 10){
			flag = 0;
			//判断是否是素数
			for(j = 2;j <= sqrt(i);j++){
				if(i % j == 0){
					flag = 1;
					break;
				}
			}
			//是素数
			if(flag == 0){
				prime[index++] = i;
			}
		}
		//如果没有则输出-1。
		if(index == 0){
			printf("-1\n");
		}
		else{
			//输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数
			for(i = 0;i < index-1;i++){
				printf("%d ",prime[i]);
			}
			printf("%d\n",prime[index-1]);
		}
	}
	return 0;
}

/*********************************
*   日期: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;
}


文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有