1029: [编程入门]自定义函数处理素数

解题思路

首先，了解下素数
素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。（即只有1跟它本身能整除掉这个数）

据此，我们可以想到 遍数法（用循环从1开始历遍）。貌似有点蠢
所以我想到了一道俺初中侄子数学证明题，

大于3的素数一定满足6n-1或6n+1(n为整数)

俺就不证明了，毕竟凭借大家的聪明才干不难证明

满足命题条件的数不一定就是素数，比如25，35，65······
所以，咱得进行进一步判断

1. 肉眼可见，6n-1或6n+1不可能被2，3，6整除。所以说我们只要历遍比要判断的数小的素数，就可以判断了

2. 为了减小运算次数，我们只要历遍比被判数的开方小的素数就可以了
   毕竟，不可能出现两个及以上大于被判数的开方的因数

废话不多说，直接上代码

#include"stdio.h"
#include"math.h"
int sushupanduan(int i) {            //函数名称比较随意 嘿嘿~
    if (i == 2 || i == 3) return 1;  //先把小于5的素数挑出来
    if (i % 6 != 1 && i % 6 != 5)    //满足命题条件的不一定是素数，不满足则一定不是
        return 0;
    else
        for (int j = 5; j <= sqrt(i); j += 6)
        {  if (i % j == 0 || i % (j + 2) == 0) return 0;  }
        //满足条件的在把比√i小的素数遍数一下就好了
}
int main(void){
    int num;
    scanf("%d", &num);
    if (sushupanduan(num)) printf("prime");
    else printf("not prime");
    return 0;
}