函数问题之寻找素数

函数问题之寻找素数

时间： 1ms        内存：128M

描述：

用函数实现操作，查找指定区间[left,right]里的素数个数，将素数保存在prime数组里并在主函数里输出。
//提交时只需提交getprime函数
#include<stdio.h>
#include<string.h>
int prime[10000];
/*
在此写函数

*/
int main()
{
    int getprime(int left,int right);
    int left,right;
    scanf("%d%d",&left,&right);
    int i,n=getprime(left,right);
    printf("%d\n",n);
    for(i=1;i<n;i++)

        printf("%d ",prime[i]); 

    if(i == n)

    printf("%d\n",prime[i]); 
    return 0;
}

输入：

一行包含两个整数，left和right(0<=left<=right<10000)。

输出：

第一行一个整数表示[left,right]内素数的个数，第二行输出区间内全部的素数，用空格隔开。

示例输入：

2 5

示例输出：

3
2 3 5

提示：

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

#include<stdio.h>
#include<string.h>
int prime[10000];

int getprime(int left,int right)
{
    if(right<2)
        return 0;
    if(left<=2)
        left=2;
    int i,j,o=0;
    for(i=left;i<=right;i++){
        for(j=2;j*j<=i;j++)
            if(i%j==0)
                break;
        if(j*j>i){
            o++;
            prime[o]=i;
        }
    }
    return o;
}
int main()
{
	int getprime(int left,int right);
	int left,right;
	scanf("%d%d",&left,&right);
	int i,n=getprime(left,right);
	printf("%d\n",n);
	for(i=1;i<n;i++)
		printf("%d ",prime[i]);
        if(i == n)
	printf("%d\n",prime[i]);
	return 0;
}

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

#include<stdio.h>
#include<string.h>
int prime[10000];

int getprime(int left,int right)
{
    int a[right+1],i,j,b=1;
    for(i=2;i<=right;i++)
        a[i]=0;
    for(i=2;i<=right;i++)
        if(a[i]==0)
    {
        if(i<=right&&i>=left)
        {prime[b]=i;
        b++;}
    for(j=i+i;j<=right;j=j+i)
        a[j]=1; }
    return b-1;
}
int main()
{
	int getprime(int left,int right);
	int left,right;
	scanf("%d%d",&left,&right);
	int i,n=getprime(left,right);
	printf("%d\n",n);
	for(i=1;i<n;i++)
		printf("%d ",prime[i]);
        if(i == n)
	printf("%d\n",prime[i]);
	return 0;
}

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