问题 1084: 用筛法求之N内的素数。

时间限制: 1Sec 内存限制: 64MB 提交: 8861 解决: 5268

题目描述

用筛法求之N内的素数。

输入

N

输出

0～N的素数

样例输入

100

样例输出

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

方法一：

import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * User: 76147
 * Date: 2020-01-27
 * Time: 13:25
 * Description:
 */
public class 用筛法求之N内的素数 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            for (int i = 0; i < n; i++) {
                if (ss(i)) {
                    System.out.println(i);
                }
            }
        }
    }

    private static boolean ss(int i) {
        if (i < 2) {
            return false;
        }
        int flag = 0;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                flag++;
            }
        }
        if (flag != 0)
            return false;
        return true;
    }
}

方法二：

import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * User: 76147
 * Date: 2020-01-27
 * Time: 13:39
 * Description:
 */
public class 用筛法求之N内的素数2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int arr[] = new int[10001];
            arr[0] = arr[1] = 1;
            for (int i = 1; i < n + 1; i++) {
                if (arr[i] == 0) {
                    for (int j = i + i; j < n + 1; j += i) {
                        arr[j] = 1;
                    }
                }
            }

            for (int i = 0; i < n + 1; i++) {
                if (arr[i] == 0)
                    System.out.println(i);
            }
        }
    }
}