素数筛法——1. 素数判定

素数判定问题

题目描述

给定一个数n，要求判断其是否为素数（0,1，负数都是非素数）。

输入描述:

测试数据有多组，每组输入一个数n。

输出描述:

对于每组输入,若是素数则输出yes，否则输入no。

示例1

输入

13

输出

yes

解题心得：

• 素数：只能被自身和1整除的大于1的正整数。
• 算法：用所有大于1小于等于sqrt(n)的整数去试着整除该数，若在该区间内存在某个数能整除该数则该数不是素数；若这些数都不能整除它，则该数为素数。时间复杂度（O（sqrt(n)））。

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

int main(){

   int m;
   while(scanf("%d",&m)!=EOF){
    int i;
    if(m<=1){
        printf("no\n");
        continue;
    }
    for(i=2;i<=sqrt(m);i++){
        if(m%i==0)
            break;
    }
    if(i<=sqrt(m)){
        printf("no\n");
    }
    else{
        printf("yes\n");
    }

   }
    return 0;

}

如果觉得有帮助，就点个赞再走吧^_^