[Project Euler] 47. 서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우는?

47. 서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우는?

서로 다른 두 개의 소인수를 갖는 수들이 처음으로 두 번 연달아 나오는 경우는 다음과 같습니다.

14 = 2 × 7
15 = 3 × 5

서로 다른 세 개의 소인수를 갖는 수들이 처음으로 세 번 연속되는 경우는 다음과 같습니다.

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우를 찾으세요. 그 첫번째 숫자는 얼마입니까?

Click  첫번째 방법. 단순한 brute-force 로... 2.5초 정도 걸리네요.

<script language="Javascript" type="text/javascript">
function func047(n){
    var t = n;
    var cnt = 0;
    if(t%2==0){
        cnt ++;
        do t/=2; while(t%2==0);
    }
    if(t%3==0){
        cnt ++;
        do t/=3; while(t%3==0);
    }
    for(var i=5; i<=t; i+=6){
        if(t%i==0){
            cnt ++;
            do t/=i; while(t%i==0);
        }
        if(t%(i+2)==0){
            cnt ++;
            do t/=i+2; while(t%(i+2)==0);
        }
    }
    return cnt;
}
function p047(){
    var cnt = 4;
    for(var i=1; cnt>0; i++){
        if(func047(i) == 4)
            cnt--;
        else
            cnt = 4;
    }
    alert(i-4);
}
</script>

두번째 방법. 위의 방법에 단순하게 이전 기록을 저장하면서 이전 기록을 참조. 0.05초? 그 이하도 나오는 듯하네요.

<script language="Javascript" type="text/javascript">
function func047(n,nums){
    if(n<2) return 0;
    if(n%2==0){
        nums[n] = (n==2)?1:(nums[n/2] + ((n%4==0)?0:1));
        return nums[n];
    }
    if(n%3==0){
        nums[n] = (n==3)?1:(nums[n/3] + ((n%9==0)?0:1));
        return nums[n];
    }
    for(var i=5; i*i<=n; i+=6){
        if(n%i==0){
            nums[n] = nums[n/i] + ((n%(i*i)==0)?0:1);
            return  nums[n];
        }
        if(n%(i+2)==0){
            nums[n] = nums[n/(i+2)] + ((n%((i+2)*(i+2))==0)?0:1);
            return nums[n];
        }
    }
    nums[n] = 1;
    return 1;
}
function p047(){
    var nums = [0,0];
    var cnt = 4;
    for(var i=1; cnt>0; i++){
        if(func047(i,nums) == 4)
            cnt--;
        else
            cnt = 4;
    }
    alert(i-4);
}
</script>

46번부터 시간을 체크하기 시작했는데 javascript는 시도할때마다 시간 오차가 좀 있네요.