C语言质数

判断质数

请对于给定的一个大于 1的正整数 N（你可以认为测评机给出的 N均小于 1000），判定它是否是一个质数。

输入格式

测评机会反复运行你的程序。每次程序运行时，你的程序仅需输入一个符合描述的正整数。

输出格式

输出也仅为一行，如果判题机在输入中给出的数字为质数，那么请输出YES；否则，请输出NO。

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

int is_prime(int n) {
    for (int i = 2，I = sqrt(n); i <= I; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        printf("%s\n", is_prime(n)? "Yes" : "No");
    }
    return 0;
}

输出小于指定值的质数

请对于给定的一个大于 1 的正整数 N（你可以认为测评机给出的 N 均小于 1000），按从小到大的顺序输出所有小于等于它的质数。
输入格式

测评机会反复运行你的程序。每次程序运行时，你的程序仅需输入一个符合描述的正整数。
输出格式

请按从小到大的顺序输出所有小于等于 N 的质数，一个数单独占一行。

方法一：

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    int i,j;
    if (n >= 2) printf("2\n");
    for(i=3; i<=n; i+=2){
        for(j=3; j<i; j+=2){
            if(i % j == 0){
                break;
            }
        } if(i == j){
            printf("%d\n", i);
        }
    }
    return 0;
}

方法二：利用函数，先判断再输出

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

int is_prime(int n) {
    for (int i = 2, I = sqrt(n); i <= I; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
       if (is_prime(i))
       printf("%d\n", i);
    }
    return 0;
}

素数筛

#include <stdio.h>
#include <math.h>
#define MAX_N 100

int prime[MAX_N + 5] = {0};

void init() {
    for (int i = 2; i <= MAX_N; i++) {
        if (prime[i]) continue;
        prime[++prime[0]] = i;
        for (int j = i ; j <= MAX_N / i; j ++) {
            prime[j * i] = 1;
        }
     }

    return ;
}
int main() {
    init();
    for (int i = 1; i <= prime[0]; i++) {
        printf("%d\n", prime[i]);
    }
    return 0;
}