`
thecloud
  • 浏览: 871922 次
文章分类
社区版块
存档分类
最新评论

简单的素数问题(2008年北京航空航天大学计算机研究生机试真题)

 
阅读更多
题目描述:

输入一个整数n(2<=n<=10000),要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数,如果没有则输出-1。

输入:

输入有多组数据。
每组一行,输入n。

输出:

输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开,最后一个素数后面没有空格),如果没有则输出-1。

样例输入:
100
样例输出:
11 31 41 61 71

代码:

#include <stdio.h>
#include <math.h>

#define  bool _Bool
#define true 1
#define false 0
#define MAX 10001

bool prim[MAX];
void init()
{
    int i;
    for(i = 0;i <= MAX;i++)
        if(i % 2 == 1) prim[i] = true;
        else prim[i] = false;
}
void select()
{
    int i,j;
    int n = sqrt(MAX);
    for(i = 3;i <= n;i += 2)
    {
        if(prim[i])
        {
            for(j = i + i;j < MAX;j += i) prim[j] = false;
        }
    }
}
int main()
{
    int n;
    int i;
    init();
    select();
    while(scanf("%d",&n) != EOF)
    {
        if(n < 11) printf("-1");
        else
        {
            printf("11");
            for(i = 12;i < n;i++)
            {
                if(i % 10 == 1 && prim[i] == true) printf(" %d",i);
            }
        }

        printf("\n");
    }
    return 0;
}

详细看http://blog.csdn.net/yming0221/article/details/6087559
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics