기본적인 알고리즘 문제 풀기(Project Euler) - 1

기본적인 알고리즘 문제 풀기

문제 1. 

10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다.

1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?

package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method1();
    }
}
 
 
class MyClass1{
    
    // 문제1. 
    // 10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다.
    // 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?
    public void method1(){
        int threeMulti = 0;
        int fiveMulti = 0;
        int sum = 0;
        
        for(int i=0; i<1000; i++){
            if( i%3 == 0 ){
                threeMulti += i;
            }
            if( i%5 == 0){
                fiveMulti += i;
            }
        }
        System.out.println("3의 배수: "+threeMulti);
        System.out.println("5의 배수: "+fiveMulti);
        sum = threeMulti+fiveMulti;
        System.out.println("3의배수와 5의 배수를 모두 합한 값: "+sum); ;
    }
}

출력결과

문제 2.

피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까? 

package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method2();
    }
}
 
 
class MyClass1{
        
    // 문제2.     
    // 피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.
    // 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
    // 짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까? 
    public void method2(){
        
        int previousData = 1;
        int currentData = 2;
        int nextData = previousData + currentData; // 3
        int sum = 0;
        
        while(previousData < 4000000){            
            previousData = currentData; // 2 
            if(previousData < 4000000 ){
                currentData = nextData;  // 3
                nextData = previousData + currentData; // 5 
                System.out.println("previousData: "+previousData);
                System.out.println("currentData: "+currentData);
                System.out.println("nextData: "+nextData);                
                if(previousData % 2 == 0){
                    sum = sum+ previousData;
                    System.out.println("pre짝수값: "+previousData);
                }
            }
        }
        System.out.println("짝수값: "+sum);
    }
}    

출력 결과

문제 3.

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.

예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. // 1, 2, 3, 5, 7, 11

600851475143의 소인수 중에서 가장 큰 수를 구하세요.

package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method3();
    }
}
 
 
class MyClass1{
        
    // 문제3.     
    // 어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
    // 예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. // 1, 2, 3, 5, 7, 11
    // 600851475143의 소인수 중에서 가장 큰 수를 구하세요.    
    public void method3(){
        long n = 13195;
        
        // 정적 배열 사용
        long[] myNum1 = new long[10];
        long j = 0;
        long max = 0;
        
        // 동적배열에 사용하는 ArrayList
        ArrayList<Long> array = new ArrayList<Long>();
        
        for(long i=2; i<=n; i++){ // 2639
            if(n % i == 0){
                n = n / i;
                myNum1[(int) j++] = i;
                array.add(i);
            }
        }
        long maxValue = Collections.max(array);
        System.out.println("동적배열 최대값: "+maxValue);
        
        // 정적 배열 비교
        for(int i=0;i<j;i++){
            max = myNum1[0]; 
            if(max < myNum1[i]){
                max = myNum1[i];
            }
        }
        System.out.println("정적배열 최대값: "+max);
    }
}
 

출력 결과