알고리즘 알고가자(2)

jaden_94·2020년 9월 15일
0

소수 구하기

소수란? 1과 자기자신 만을 약수로 가지는수

  1. 정수 n이 소수라면 1부터 n-1로 나눈 나머지가 0인 경우가 없어야한다.
  2. 따라서 2 이외의 짝수는 소수일 수 없다.
  3. 정수 n 보다 작은 소수들로 나누어 떨어지면 소수가 아니다.(1부터 n-1까지 모두 나누어 볼 필요없이, 그 중 소수들로 나누어 보면 된다)
  4. n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.

JAVA 코드로 parameter로 들어온 값이 소수인지 확인 하는 코드를 구현해 보자

boolean isPrime(int number){
	for(int i = 2; i*i <= number; i++){
    	if(number % i == 0) return false;
    }
    return true;
}

JAVA 코드로 1000까지의 양의 정수 중 소수를 찾는 코드를 구현해 보자

ArrayList<Integer> prime = new ArrayList<>();  //찾은 소수들
        prime.add(2);
        prime.add(3);
        for(int n = 5; n <= 1000; n++){
            boolean flag = false;
            for(int i = 0; prime.get(i)*prime.get(i) <= n; i++){
                if(n%prime.get(i) ==0 ){
                    flag = true;
                    break;
                }
            }
            if(!flag)
                prime.add(n);
        }

그 해의 경과일수 구하기

고려해야할 사항
윤년
4로 나누어 떨어지는 해는 윤년, 그 밖의 해는 평년으로 한다.
4로 나누어 떨어지지만 100으로도 나누어 떨어지는 해는 평년으로 한다.
단, 400으로 나누어 떨어지는 해는 윤년으로 한다.(예: 2000년, 2400년)

JAVA 코드로 그 해의 경과일수를 출력하는 메소드를 구현해보자

  static int[][] mdays ={
  	     	{31,29,31,30,31,30,31,31,30,31,30,31},
  			{31,28,31,30,31,30,31,31,30,31,30,31}
  		};
  
  static int isLeap(int year){     // true -> 1
        return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0 ) ? 1 : 0;
    }
  
  static int dayOfYear(int y, int m, int d){
        int days = d;  // m 월의 일 수
        for(int i = 1; i < m; i++){
            days += mdays[isLeap(y)][i-1]; // m월 이전 월들의 일 수
        }
        return days;
    }
  • && 은 || 보다 우선순위가 높은 연산자이다. 즉,
    year % 4 == 0 && year % 100 != 0 || year % 400 == 0
    (year % 4 == 0 && year % 100 != 0) || year % 400 == 0
    같은 코드가 된다.

0개의 댓글