#009 소수 판별

#문제)

1부터 100까지 숫자 중에서 가장 큰 소수를 반환하여라

ex) 2, 3, 5, 7, 11, 13, 17 …

규칙성)

2부터 시작하여 n까지 반복하면서 

증가되는 숫자보다 작은수를 %연산하여 결과가 0이 하나라도 나오면 자연수로 판단한다.

*여기서 작은 수란? 자신과 1을 제외한 수

여기 문제에서는 가장 큰 소수를 반복하라 하였으니 100부터 시작하면 더 빠르게 구할 수 있다.

package dataStructure.prediction.problem;

import java.util.LinkedList;

import java.util.List;

public class PrimeNumber {

   

    private List<Integer> array = new LinkedList<Integer>();

   

    public PrimeNumber() {

        // TODO Auto-generated constructor stub

    }

   

    public void execute() {

        int n = 100;

        for(int i=n; i>=2; i--) {

            if(isPrimeNumber(i)) {

                array.add(i);

            }

        }

    }

    private boolean isPrimeNumber(int n) {

        boolean isPrimeNumber = true;

        int value = n-1;

        while(value>2) {

            if((n % value) == 0) {

                isPrimeNumber = false;

            }

            value--;

        }

        return isPrimeNumber;

    }

   

    public void print() {

        for(Integer val : array) {

            System.out.printf("%2d ",val);

        }

        System.out.println();

    }

   

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        PrimeNumber prime = new PrimeNumber();

        prime.execute();

        prime.print();

    }

}

여기서 끝내려 했으나 응용문제까지 풀어보자

#응용문제)

1부터 50000까지 소수를 모두 반환하여라

물론, 적은 수의 프로그램에서도 효율성을 고려하면 좋겠지만 

문제에서 제시하는 숫자가 커지니 확실히 효율성에 대한 압박감이 더욱 커진다.

위와 같은 방식도 좋지만

한가지 더 개선할 부분이 있다.

소수 여부를 판단할 때 

자신보다 작은 수 -> 자신보다 작은 소수로 계산해도 결과가 같다

즉 %할 연산 수를 줄이는 것이다.

package dataStructure.prediction.problem;

import java.util.LinkedList;

import java.util.List;

public class PrimeNumber {

   

    private List<Integer> array = new LinkedList<Integer>();

    public PrimeNumber() {

        // TODO Auto-generated constructor stub

    }

   

    public void execute() {

        int n = 100;

        for(int i=2; i<=n; i++) {

            if(isPrimeNumber(i)) {

                array.add(i);

            }

        }

    }

    private boolean isPrimeNumber(int n) {

        boolean isPrimeNumber = true;

        for(int i=0;i<array.size(); i++) {

            if((n % array.get(i)) == 0) {

                isPrimeNumber = false;

            }

        }

        return isPrimeNumber;

    }

   

    public void print() {

        for(Integer val : array) {

            System.out.printf("%2d ",val);

        }

        System.out.println();

    }

   

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        PrimeNumber prime = new PrimeNumber();

        prime.execute();

        prime.print();

    }

}