dev80

//

//  main.c

//  project euler

//

//  Created by 김일호 on 2015. 4. 25..

//  Copyright (c) 2015년 김일호. All rights reserved.

//

#include <stdio.h>

int main(int argc, const char * argv[]) {

    int product = 0;

    for(int i =1; i<1000; i++)

        for (int j = 1; j<1000; j++){

            for (int k = 1; k<1000; k ++)

            {

                if( j < i && k < j)

                    break;

                if((i * i) + (j * j) == (k*k))

                {

                    product = i+j+k;

                    if(product == 1000)

                    {

                        printf("%d %d %d",i, j, k);

                        return 0;

                    }

                }

                else if (k+j>1000)

                {product = 0;break;}

                else if (k+i>1000)

                {product = 0;break;}

                product = 0;

            }

            if(i+j>1000){

                product = 0;

               break;

            }

        }

    return 0;

}

문제: 소수 중 처음 6개를 나열하면 2, 3, 5, 7, 11, 13 이다. 이 때 6번째 소수는 13이다.

10001번째 소수는 무엇인가?

#include <stdio.h>

int main(){

    int count=0;

    int i;

    int j;

    for(i=2;;i++){

        for(j=2;j<=i;j++){

            if(i==j){

                count++;

                break;

            }

            else if((i%j)==0){

                break;

            }

        }

        if(count==10001) {break;}

    }

    printf("%d\n", i);

}

문제: 1부터 10까지의 자연수의 제곱의 합은 아래와 같습니다.

12 + 22 + ... + 102 = 385

1부터 10까지의 자연수의 합의 제곱은 아래와 같습니다.

(1 + 2 + ... + 10)2 = 552 = 3025

1부터 10까지의 자연수의 합의 제곱과 제곱의 합의 차는 3025 - 385 = 2640 입니다.

1부터 100까지의 자연수의 합의 제곱과 제곱의 합의 차는 얼마인가요?

#include <stdio.h>

int main(){

    int a=0;

    int b=0;

    int i;

    for(i=1;i<=100;i++)

        a += (i*i);

    for(i=1;i<=100;i++)

        b += i;

    b = b*b;

    printf("%d\n", b-a);

}

1번보다 쉬운거 같습니다.

문제: 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

문제를 푼 알고리즘이 있는데 코딩으로 적용시키는 것이 까다로워서 일단 알고리즘 설명만 남기도록 하겠습니다.

제가 푼 알고리즘은 

문제에서 제시된 2520을 소인수분해 하여 찾았습니다.

2520= 2^3 * 3^2 * 5 * 7

이며, 소인수분해를 보시면 1~10까지 소인수를 조합하여 모든 수를 표현 가능 합니다.

그럼 이 수에 11~20의 소수를 먼저 곱하고

X = 2^3 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

11~20사이의 수를 표현 가능한지 확인 합니다.

2^4인 16이 표현 되지 못하는군요. 저 윗식에 2를 곱합니다.

X = 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

소인수를 보시면 1~20의 수 모두 표현이 가능하므로 정답이 되겠습니다.

PS) 해답을 보면 제가 풀은 알고리즘을 예시로 들고 log를 이용하여 새로운 식(일반해?라고 해야할까요)을 정의합니다.

문제: 앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 x 99) 입니다.

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까 ?

#include <stdio.h>
int main() {
int i, j;
int x;
int sol = 0;
int n1, n2, n3, n4, n5, n6;
for (i = 999; i > 100; i - )
	for (j = 999; j > 100; j - ){
		x = i * j;
		n1 = x / 100000;
		x = x % 100000;
		n2 = x / 10000;
		x = x % 10000;
		n3 = x / 1000;
		x = x % 1000;
		n4 = x / 100;
		x = x % 100;
		n5 = x / 10;
		x = x % 10;
		n6 = x / 1;
		if ((n1 == n6) && (n2 == n5) && (n3 == n4)){
			printf("n1 = %d,n2 = %d,n3 = %d,n4 = %d,n5 = %d,n6 = %d \n", n1, n2, n3, n4, n5, n6);
			x = i*j;
			if (x > sol){
				sol = x;
				break;
			}
		}
	}
printf("%d \n", sol);
}

3자리 x 3자리로 이루어진 가장 큰 대칭수는 6자리라고 단정 짓고 짠 알고리즘,

해답:

대칭수 P는 x,y,z로 구성 가능. P= a x b(a와 b는 100보다 크고 999보다 작은 정수)

P는 반드시 적어도 6자리로 긴 정수 일것이다. 왜냐하면 111111=143 x 777 이기 때문(P는 3자리 x 3자리로 이루어진 대칭수 111111보다 크거나 같을 것)

따라서,

P=100000x+10000y+1000z+100z+10y+x

P=100001x+10010y+1100z 

P=11(9091x+910y+100z)

11은 소수로 반드시 a, b는 11을 약수로 가짐

따라서 11로 나누어 지지 않는다면 대칭수가 아님.

largestPalindrome = 0

a = 999

while a >= 100

if a mod 11 = 0

b = 999

db = 1

else

b = 990 //The largest number less than or equal 999

 //and divisible by 11

db = 11

while b >= a

if a*b <= largestPalindrome

break

if isPalindrome(a*b)

largestPalindrome = a*b

b = b-db

a = a-1

output largestPalindrome

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

예를들면 13195의 소인수는 5, 7, 13, 29 입니다. 600851475143의 소인수 중에서 가장 큰 수를 구하세요.

#include <stdio.h>

int main()

{

 int i;

 unsigned long long int n = 600851475143;

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

 {

  if (n%i == 0){

   printf("%d ", i);

   n = n/i;

   i = 2;

  }

 }

 return 0;

}

//문제의 답이 제대로 나오지 않았는데, INT형의 범위를 고려하지 않은것이 문제였다. unsigned long long으로 선언하지 않으면 제대로 된 답이 나오지 않는다.

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

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

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

#include <stdio.h>

int main()

{

 int first = 1;

 int second = 2;

 int third = 0;

 unsigned int total = 2;

 int flag = 0;

 while (third < 4000000){

  third = first + second;

  if (third % 2 == 0) total += third;

  first = second;

  second = third;

 }

 printf("%d\n", total);

}