소수를 찾아내는 알고리즘에는 크게 두가지 방법이 있다.

1. 무식하게 약수의 갯수를 구하는 방법

2. 에라토스테네스의 체를 이용하여 푸는 방법

에라토스테네스의 체를 이용하여 푸는 방법의 원리는 다음과 같다.

- 2부터 n까지의 수를 쭉 적고, 목록에서 지워지지 않는 수들을 순회함, 수의 배수를 지우기를 반복하다가

그 다음으로는 3의 배수를 모두 지우고, 5의 배수를 지우고, 7의 배수를 지우고... 쭉 제거를 하다 보면

남는 수들이 있는데 이를 체로 거른 뒤 남는 수들이 모두 결국 소수가 된다.

(그림 출처 : http://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4)

체를 이용하여 연산할 경우 부하가 확 줄어드니 한번쯤 적용해서 풀어보는 것도 좋을 것 같다.

부분 구간은 연습 구간의 합을 구해야 되는 문제일 경우

1. 배열 이용해서 풀이 가능

2. 무슨소리인고 하면,

arr    -2    9    2    -6    7    -7    5

sum    0    -2    7    9    3    10    3    

============================

구간 2~4 = sum[5] - sum[2]

(10 -7 = 3)

============================

결국 arr[i]~[j]의 구간 합은 sum(j+1) - sum(j)

위와 같은 느낌으로 잡아주면 된다....

아인쉬타인 생일날 그는 가장 친한 두명의 친구를 파티에 초대했다. 그의 생일이 3 월 14일 파이 데이 여서 생일케익 대신에 생일파이를 준비했다.

그의 두 친구가 차례대로 파이의 일부분을 가지고 간 후 그가 남은 파이가 얼마가 될지를 알고자 한다. 우리가 할 일은 그를 도와서 남은 파이가 얼마인지를 알아내는 것이다.

입력

입력으로 두 줄이 주어지고 각 줄은 친구 한 명이 먹는 파이의 양이 분수로 입력된다. 첫수가 분자 , 두 번째 수가 분모이다.

두 분수의 합은 1 을 넘지 않는다.

출력

남은 파이의 양을 출력한다. 만약 남은 파이의 양이 없으면 0 을 출력하고 아니면 기약분수로 출력한다.

입출력 예

입력

1 4

1 4

출력

1/2

입력

1 4

2 3

출력

1/12

입력

33 99

66 99

출력

0

입력

2 17

5 23

- 케이크가 있는데, 전체의 량을 1로 잡고, 각각 두사람이 나눠 먹을시 남아있는 케이크가

얼마나 남았는지를 확인하는 알고리즘

-> 유클리드 호제법으로 풀이 가능함