[Project Euler] Problem 003

예전에 Java로 풀었던 문제다.

public class Problem003 {
    public static void main(String[] args) {
        long num = 600851475143L;
        int[] primeFactors = new int[100];
        int idx = 0;
        int i = 2;
        
    
        while((num / i != 1) || (num%i != 0)) {
            if(num%i == 0) {
                primeFactors[idx++] = i;
                num /= i;
            } else {
                i++;
            }
            
            
            if () {
                primeFactors[idx] = i;
                break;
            }
        }
        
        primeFactors[idx] = i;
        
        
        for(int j = 0; j < primeFactors.length; ++j) {
            if((primeFactors[j] != 0) && (primeFactors[j + 1] == 0)) {
                idx = j;
                break;
            }
        }
        
        System.out.println("The largest prime factor: " + primeFactors[idx]);
    }
}

18행의 조건문에 조건이 없다.

뭘 실험해본다고 코드 일부를 수정하는 과정에서 지워졌는데 그걸 실수로 저장한 모양이다.

대체 왜....

그리고 코드도 너무 복잡한 것 같아서 C로 다시 풀었다.

#include <stdio.h>
 
int run();
 
int main()
{
    return run();
}
 
int run()
{
    long long number = 600851475143;
    long long pf = 3;
    long long max = -1;
 
    while (number > 1)
    {
        if (number % pf == 0)
        {
            number /= pf;

            if (max < pf) { max = pf; }
        }
        else
        {
            ++pf;
        }
 
    }
 
    printf("%lld\n", max);
 
    return 0;
}

제수를 늘리며 나누어지는지 확인한다.

단, 소인수는 중복될 수 있으므로 나누어지지 않을 때만 제수의 값을 늘린다.

모든 소인수로 나눠지면  number 는  1 이 되므로 반복문의 탈출 조건은  number > 1 이 된다.