c语言超过时间限制

Question

#include<stdio.h>
main()
{
int i,k,n,f,s;
scanf("%d",&k);
f=3;
for(;f<=k;f++)
{n=1;
for(i=2;i<f;i++)
if(f%i==0)
{n=0;
i=f;
}
if(n==1)
s=f;
}
printf("The max prime number is %d.\n",s);
}
题目是求小于一个数的最大素数

Answer 1

从你的程序可以看出，是在求"从键盘输入一个大于2的整数k，输出不大于k的最大的素数。"你的程序尽管也可找出来，但选择的算法效率太低，你是从小到大逐一判断，然后取其最大的，这种方法需先求出不大于k的所有的素数，效率当然低了。正解是从大到小逐一判断，遇到的第一个素数即为不大于k的最大素数。程序可如下
#include <stdio.h>
#include <math.h>
void main( ) {
int i, k, n, f, s;
scanf("%d", k);
for(n = 0, f = k; !n && (f > 1); f--)
{
for(n = 1, i = 2, s = sqrt(f); n && (i <= s); i++)
if(f % i == 0) n = 0;
}
printf("The max prime number is %d\n", f);
}

Answer 2

程序错了吧，题目是什么追问

求小于一个数的最大素数

追答

#include
#include
int main()
{
int i,k,n,s=0;
int f;
printf("please input a integer(>2): ");
scanf("%d",&k);
f=sqrt(k);
n=k-1;
if(n==2) s=n;
else
{
for(n;n>=2;n--)
{
for(i=2;i<=f;i++)
{
if(n%i==0) break;
if(i==f) s=n;
}
if(s!=0) break;
}
}
printf("The max prime number is %d.\n",s);
return 0;
}