소수 찾기

입력한 정수까지 모두 체킹을 하며 소수를 찾는 방식

<코드>

import java.util.Scanner;

public class ListPrimes {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("정수를 입력하세요: ");
        int num = sc.nextInt();
        int cnt = 0;

        for (int i = 2; i <= num; i++){
            boolean isPrime = true;
            for (int j = 2; j < i ; j++){
                cnt++;
                if (i % j == 0){
                    isPrime = false;
                    break;
                }
            }
            if(isPrime == true){
                System.out.println(i);
            }
        }
        System.out.println(cnt);
    }
}

 

<설명>

1. 입력한 정수까지의 모든 수를 2부터 체킹하는 수-1까지의 모든 수로 나누어 소수인지 판별을 한다
2. 이러한 방식은 시간이 오래걸리는 단점이 있음

입력한 정수까지 홀수만 체킹을 하며 소수를 찾는 방식

<코드>

mport java.util.Scanner;

public class ListPrimes2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("정수를 입력하세요: ");
        int num = sc.nextInt();
        int cnt = 0;
        int arrCnt = 0;
        int[] primes = new int[500];

        primes[arrCnt++] = 2; // 2를 먼저 소수의 배열에 넣어준다.

        for (int i = 3; i <= num; i+=2){
            boolean isPrime = true;
            for (int j = 3; j < i ; j++){
                cnt++;
                if (i % j == 0){
                    isPrime = false;
                    break;
                }
            }
            if(isPrime == true){
                System.out.println(i);
            }
        }
        System.out.println(cnt);
    }
}

 

<설명>

1. 2를 먼저 소수의 배열 primes에 넣어준다.
2. 3부터 입력한 정수까지 홀수만 체킹을 하며 그 사이의 수로 모두 나누며 소수인지 판별한다.
3. 위의 코드와 다르게 prime배열에 3을 먼저 넣어주고 5부터 판별해도 된다. (2, 3 모두 소수이기 때문이다.)