素数判定
标签: 机试攻略 - 高分篇
学习人数: 19.0k


高清播放
赞赏支持

如何判断一个数x是不是素数呢?

我们可以根据素数的定义从2到小于这个数x的每个数去除,看是否能除尽。
一般情况下,我们没有必要判断这么多个数,只用判断到sqrt(x)就停止了。

因为:如果比sqrt(x)大的数能除尽的话,就必然存在一个比sqrt(x)小的数能被除尽。

 

判断素数
题目描述:
输入一个整数,判断该整数是否为素数,若是,输出该整数,若否,输出大于该整数的第一个素数。(例如,输入为14,输出17,因为17是大于14的第一个素数)
输入描述:
输入一个整数n,n最大为10000。
输出描述:
按题意输出。
输入样例#:
14
输出样例#:
17
题目来源:
DreamJudge 1013

题目解析:我们首先判断输入的n是不是一个素数,如果是的话就直接输出。如果不是的话,我们从n+1开始,对每个数去判断它是不是一个素数,直到找到一个素数的时候终止。

 

参考代码

#include <stdio.h>  
#include <math.h>  
  
int main() {  
    int n;  
    scanf("%d", &n);  
    if (n == 1) n++;//1不是素数  
    for (int i = n; ; i++) {  
        int flag = 0;  
        for (int j = 2; j <= sqrt(i); j++) {  
            if (i % j == 0) {//如果找到了约数  
                flag = 1;//说明不是素数  
                break;  
            }  
        }  
        if (flag == 0) {  
            printf("%d\n", i);  
            break;  
        }  
    }  
    return 0;  
}  

 

登录查看完整内容


课后作业

练习题目

DreamJudge 1355 素数判定 - 哈尔滨工业大学


登录后开始许愿

暂无评论,来抢沙发