xuotoj 1510: 输入数值区间，求素数

1510: 输入数值区间，求素数

时间限制: 1 Sec   内存限制: 128 MB
提交: 277   解决: 136
[ 提交][ 状态][ 讨论版]

题目描述

输入数值范围，列出该范围中所有的素数。

输入

3 20

输出

3 5 7 11 13 17 19 

样例输入

3 13

样例输出

3 5 7 11 13

实际一个特别水的题，当时想法肯定是筛法,但第一次做卡了

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

int a[10001];

void get_prime(int n) {
    int i;
    int j;
    for(i = 2;i < n;i++)
        a[i] = 1;
    for(i = 2;i <= sqrt(n);i++) {
        if(a[i] == 1) {
            for(j = i*2;j < n;j += i){
                a[j] = 0;
            }
        }
    }
}
int main() {
    int i;
    int m;
    int n;
    int flag = 0;
    
    scanf("%d %d",&m,&n);
    get_prime(n);
    for(i = m;i <= n;i++) {
        if(a[i]) {
            if(flag == 0) {
                printf("%d",i);
                flag = 1;
            } else {
                printf(" %d",i);
            }
        }
    }
    
    return 0;
}

后来就直接在主函数求素数

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

int main() {
    int m;
    int n;
    int a[10001];
    int i;
    int j;

    scanf("%d %d",&m,&n);
    for(i = m; i <= n; i++) {
            a[i] = i;
    }
    a[1] = 0;

    for (i = 2; i < sqrt(n); i++) {
            for (j = i+1; j <= n; j++) {
                    if (a[j] != 0 && a[j]%i == 0) {
                            a[j] = 0;
                    }
            }
    }
    for(i = m;i <= n;i++) {
        if(a[i]) {
            printf("%d ",i);
        }
    }

    return 0;
}