C/C++ 找出最大素数 算法

24.【中学】找出最大素数

小明在中学学习了什么是素数。素数是指一个只能被1和它本身整除的数，在数论中占有重要的研究地位，在当代密码学中也被广泛应用。

输入：

取值范围

输出：

该范围内的最大素数

#include <stdio.h>  
#include <stdlib.h>  

int main(int argc, char *argv[]) {  
    int input = 0, answer = 0;
    scanf("%d", &input);
    while(input > 0)
    {
    	int flag = 1;
    	for(int i = 2; i * i <= input ;i++)
    	{
    		if(input % i == 0)
    		{
    			flag = 0;
    			break;
    		}
    	}
    	if(flag == 1 || input == 2)
    	{
    		answer = input;
    		break;
    	}
    	input--;
    }
    printf("The max prime number is %d.\n",answer);  
    return 0;  
}  

顺便提一句，最小的素数是2不是1。
而且如果n是合数的话，那么这个合数必然有小于等于根号n的因子。
大大降低了时间复杂度。