求素数

求素数

时间： 1ms        内存：128M

描述：

设计一个程序，输出所有小于等于n（n为一个大于2的正整数）的素数。输入包含多组测试数据。

要求：（1）每行输出10个素数。

            （2）尽量采用较优的算法。

输入：

50

输出：

    2     3     5     7    11     13     17   19   23   29

   31   37   41   43   47

示例输入：

50

示例输出：

    2    3    5    7   11   13   17   19   23   29
   31   37   41   43   47

提示：

参考答案（内存最优[0]）：

#include<stdio.h>
int n;
int judge(int n)
{
    int i;
    if(n==2)
        return 1;
    for(i=2;i<=sqrt(n);i++)
        if(n%i==0)
        return 0;
    return 1;
}
int main()
{
    scanf("%d",&n);
    int i,flag=1;
    for(i=2;i<=n;i++)
    {
        if(judge(i)==1)
        {
            if(flag==10)
            {
                printf("%5d\n",i);
                flag=1;
            }
            else
                {
                    printf("%5d",i);
                    flag++;
                }
        }
    }
    return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<iostream>
using namespace std;
bool isprime(int n)
{
    int i;
    for(i=2;i*i<=n;i++)
        if(n%i==0)
        return false;
    return true;
}
int main()
{
    int n,i,k;
    while(~scanf("%d",&n))
    {
        k=0;
        for(i=2;i<=n;i++)
        {
        if(isprime(i))
            {k++;printf("   %2d",i);
            if(k%10==0)cout<<endl;}
        }
        printf("\n");
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。