Question

C语言：输入一个正整数n，求第n小的质数。

怎样才能运算提高效率

描述

输入一个正整数n，求第n小的质数。

输入

一个不超过10000的正整数n。

输出

第n小的质数。

样例输入 10

样例输出 29

（我的程序）

#include<stdio.h>

int main()

{

int n,num=0,i=2,x,y,m=0;

scanf("%d",&n);

for(i=2;;i++)

{

num=0;

y=i;

for(x=1;x<i;x++)

{

if(y%2==0 && y!=2)

{

num+=2;

break;

}

if(y%3==0 && y!=3)

{

num+=2;

break;

}

if(y%5==0 && y!=5)

{

num+=2;

break;

}

if(y%7==0 && y!=7)

{

num+=2;

break;

}

if(y%x==0)

num++;

if(num>=2)

break;

}

if(num<=1)

m++;

if(m==n)

break;

}

printf("%d\n",i);

return 0;

}

Answer 1

①先定义个函数isfun();如果是素数返回1，如果不是返回0

int isfun(int n){//判断素数函数
{
    for(i=2;i<=sqrt(n);i++) 
        if(n%i==0)
            return 0;
    return 1;
}

②从n向下递减，依次调用isfun()判断是否是素数,如果是输出该数，跳出循环。

#include<stdio.h>
int isfun(int n){
{
    for(i=2;i<=sqrt(n);i++) 
        if(n%i==0)
            return 0;
    return 1;
}
int main()
{
    int n,i;
    scanf("%d",&n);
    while(n--){
        if(isfun(n)){
            printf("%d\n",n);
            break;
            }
    }
    return 0;
}

Answer 2

#include<stdio.h>
main()
{
int m,n,s=2,j=0;
register int i;
printf("please input a number:n=");
scanf("%d",&n);
while(1)
{
for(i=2;i<=s-1;i++)
{
if(s%i==0)
{
m=s;
break;
}
}
if(m!=s)
j++;
if(n==j)
{
printf("%d\n",s);
break;
}
s++;
}
}

Answer 3

#include "math.h"
int data[50000] ={2, 3};
int cnt = 2;
int getdata(int n)
{
	while (cnt < n) {
		int i, j;
		i = data[cnt - 1];
		while (1) {
			int e;
			i += 2;
			e = sqrt(i);
			j = 1;
			while (j < cnt && 
				 i % data[j] &&
			     data[j] < e) {
				j++;
			}
			if (i % data[j]) {
				data[cnt] = i;
				cnt++;
				break;
			}
		}
	}
	return data[n - 1];
	
}
int main()
{
	while (1) {
		int n;
		scanf("%d", &n);
		printf("  %d\n", getdata(n));
	}
    return 0;
}