시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 554 283 190 53.371%

문제

양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다.

700은 상근수이다.

  • 72 + 02 + 02 = 49
  • 42 + 92 = 97
  • 92 + 72 = 130
  • 12 + 32 + 02 = 10
  • 12 + 02 = 1

2는 상근수가 아니다.

  • 22 = 4
  • 42 = 16
  • 12 + 62 = 37
  • 32 + 72 = 58
  • 52 + 82 = 89
  • 82 + 92 = 145
  • 12 + 42 + 52 = 42
  • 42 + 22 = 20
  • 22 + 02 = 4
  • 42 = 16
  • ... 끝나지 않는다

소수는 1과 자기자신을 제외하고 약수가 없는 수이다. 2, 3, 5, 7, 11, 13, 17, 19, ... 는 소수이다.

소수상근수는 소수이면서 상근수인 숫자이다. 7, 13, 19, ... 는 소수 상근수이다.

n이 주어졌을 때, n보다 작거나 같은 모든 소수상근수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n (10 ≤ n ≤ 1000000)이 주어진다.

출력

n보다 작거나 같은 소수상근수를 한 줄에 하나씩 오름차순으로 출력한다.

예제 입력 1

20

예제 출력 1

7
13
19
W3sicHJvYmxlbV9pZCI6Ijk0MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMThcdWMwYzFcdWFkZmNcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1Yzc1OCBcdWFjMDEgXHVjNzkwXHViOWFjXHVjMjE4XHVjNzU4IFx1YzgxY1x1YWNmMVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI4MDdcdWFjOGMgXHVkNTc0XHVjMTFjIFx1YjA5OFx1YzYyOCBcdWQ1NjlcdWIzYzQgXHVhYzAxIFx1Yzc5MFx1YjlhY1x1YzIxOFx1Yzc1OCBcdWM4MWNcdWFjZjFcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViODA3XHVhYzhjIFx1YmMxOFx1YmNmNVx1ZDU3NFx1YzExYyAxXHVjNzc0IFx1YjA5OFx1YzYyOFx1YjJlNFx1YmE3NCwgblx1Yzc0NCBcdWMwYzFcdWFkZmNcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD43MDBcdWM3NDAgXHVjMGMxXHVhZGZjXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjc8c3VwPjI8XC9zdXA+ICsgMDxzdXA+MjxcL3N1cD4gKyAwPHN1cD4yPFwvc3VwPiA9IDQ5PFwvbGk+XHJcblx0PGxpPjQ8c3VwPjI8XC9zdXA+ICsgOTxzdXA+MjxcL3N1cD4gPSA5NzxcL2xpPlxyXG5cdDxsaT45PHN1cD4yPFwvc3VwPiArIDc8c3VwPjI8XC9zdXA+ID0gMTMwPFwvbGk+XHJcblx0PGxpPjE8c3VwPjI8XC9zdXA+ICsgMzxzdXA+MjxcL3N1cD4gKyAwPHN1cD4yPFwvc3VwPiA9IDEwPFwvbGk+XHJcblx0PGxpPjE8c3VwPjI8XC9zdXA+ICsgMDxzdXA+MjxcL3N1cD4gPSAxPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Mlx1YjI5NCBcdWMwYzFcdWFkZmNcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjI8c3VwPjI8XC9zdXA+ID0gNDxcL2xpPlxyXG5cdDxsaT40PHN1cD4yPFwvc3VwPiA9IDE2PFwvbGk+XHJcblx0PGxpPjE8c3VwPjI8XC9zdXA+ICsgNjxzdXA+MjxcL3N1cD4gPSAzNzxcL2xpPlxyXG5cdDxsaT4zPHN1cD4yPFwvc3VwPiArIDc8c3VwPjI8XC9zdXA+ID0gNTg8XC9saT5cclxuXHQ8bGk+NTxzdXA+MjxcL3N1cD4gKyA4PHN1cD4yPFwvc3VwPiA9IDg5PFwvbGk+XHJcblx0PGxpPjg8c3VwPjI8XC9zdXA+ICsgOTxzdXA+MjxcL3N1cD4gPSAxNDU8XC9saT5cclxuXHQ8bGk+MTxzdXA+MjxcL3N1cD4gKyA0PHN1cD4yPFwvc3VwPiArIDU8c3VwPjI8XC9zdXA+ID0gNDI8XC9saT5cclxuXHQ8bGk+NDxzdXA+MjxcL3N1cD4gKyAyPHN1cD4yPFwvc3VwPiA9IDIwPFwvbGk+XHJcblx0PGxpPjI8c3VwPjI8XC9zdXA+ICsgMDxzdXA+MjxcL3N1cD4gPSA0PFwvbGk+XHJcblx0PGxpPjQ8c3VwPjI8XC9zdXA+ID0gMTY8XC9saT5cclxuXHQ8bGk+Li4uIFx1YjA1ZFx1YjA5OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMxOGNcdWMyMThcdWIyOTQgMVx1YWNmYyBcdWM3OTBcdWFlMzBcdWM3OTBcdWMyZTBcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTU4XHVhY2UwIFx1YzU3ZFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyOTQgXHVjMjE4XHVjNzc0XHViMmU0LiAyLCAzLCA1LCA3LCAxMSwgMTMsIDE3LCAxOSwgLi4uIFx1YjI5NCBcdWMxOGNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE4Y1x1YzIxOFx1YzBjMVx1YWRmY1x1YzIxOFx1YjI5NCBcdWMxOGNcdWMyMThcdWM3NzRcdWJhNzRcdWMxMWMgXHVjMGMxXHVhZGZjXHVjMjE4XHVjNzc4IFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YjJlNC4gNywgMTMsIDE5LCAuLi4gXHViMjk0IFx1YzE4Y1x1YzIxOCBcdWMwYzFcdWFkZmNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPm5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0Yywgblx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWMxOGNcdWMyMThcdWMwYzFcdWFkZmNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG4gKDEwICZsZTsgbiAmbGU7IDEwMDAwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5uXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjMThjXHVjMjE4XHVjMGMxXHVhZGZjXHVjMjE4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTQyMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhhcHB5IFByaW1lIE51bWJlciIsImRlc2NyaXB0aW9uIjoiPHA+QSBIYXBweSBOdW1iZXIgXHUyNjNhIGNhbiBiZSBkZWZpbmVkIGFzIGZvbGxvd3MuIEZyb20gYSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIGNhbGN1bGF0ZSB0aGUgc3VtIG9mIHNxdWFyZSBvZiBlYWNoIGRpZ2l0IG9mIG4uIFRoZW4gZnJvbSB0aGF0IHN1bSwgcmVwZWF0IHRoZSBzYW1lIHByb2Nlc3Mgb3ZlciBhbmQgb3ZlciBhZ2Fpbi4gVGhpcyBjeWNsZSB0ZXJtaW5hdGVzIGlmIGFuZCBvbmx5IGlmIHRoZXJlIGlzIDEgaW4gdGhlIHNlcXVlbmNlLiBIZW5jZSwgd2UgY2FsbCB0aGUgbnVtYmVyIG4gYSBoYXBweSBudW1iZXIgaWYgaXQgZ2VuZXJhdGVzIGEgZmluaXRlIHNlcXVlbmNlLiBPdGhlcndpc2UsIHRoZSBlbmRsZXNzIGN5Y2xlIG9jY3VycyAoMSBuZXZlciBhcHBlYXJzIGluIHRoZSBzZXF1ZW5jZSkuIFdlIG1heSBjYWxsIHRoZSBudW1iZXIgZ2VuZXJhdGluZyBhbiBlbmRsZXNzIGN5Y2xlIGFuIHVuaGFwcHkgbnVtYmVyIC4gT2JzZXJ2ZSB0aGUgZm9sbG93aW5nIGV4YW1wbGVzOiZuYnNwOzxcL3A+XHJcblxyXG48cD43MDAgaXMgYSBoYXBweSBudW1iZXImbmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT43PHN1cD4yPFwvc3VwPiZuYnNwOysgMDxzdXA+MjxcL3N1cD4mbmJzcDsrIDA8c3VwPjI8XC9zdXA+Jm5ic3A7PSA0OTxcL2xpPlxyXG5cdDxsaT40PHN1cD4yPFwvc3VwPiZuYnNwOysgOTxzdXA+MjxcL3N1cD4mbmJzcDs9IDk3PFwvbGk+XHJcblx0PGxpPjk8c3VwPjI8XC9zdXA+Jm5ic3A7KyA3PHN1cD4yPFwvc3VwPiZuYnNwOz0gMTMwPFwvbGk+XHJcblx0PGxpPjE8c3VwPjI8XC9zdXA+Jm5ic3A7KyAzPHN1cD4yPFwvc3VwPiZuYnNwOysgMDxzdXA+MjxcL3N1cD4mbmJzcDs9IDEwPFwvbGk+XHJcblx0PGxpPjE8c3VwPjI8XC9zdXA+Jm5ic3A7KyAwPHN1cD4yPFwvc3VwPiZuYnNwOz0gMTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjIgaXMgbm90IGEgaGFwcHkgbnVtYmVyJm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MjxzdXA+MjxcL3N1cD4mbmJzcDs9IDQ8XC9saT5cclxuXHQ8bGk+NDxzdXA+MjxcL3N1cD4mbmJzcDs9IDE2PFwvbGk+XHJcblx0PGxpPjE8c3VwPjI8XC9zdXA+Jm5ic3A7KyA2PHN1cD4yPFwvc3VwPiZuYnNwOz0gMzc8XC9saT5cclxuXHQ8bGk+MzxzdXA+MjxcL3N1cD4mbmJzcDsrIDc8c3VwPjI8XC9zdXA+Jm5ic3A7PSA1ODxcL2xpPlxyXG5cdDxsaT41PHN1cD4yPFwvc3VwPiZuYnNwOysgODxzdXA+MjxcL3N1cD4mbmJzcDs9IDg5PFwvbGk+XHJcblx0PGxpPjg8c3VwPjI8XC9zdXA+Jm5ic3A7KyA5PHN1cD4yPFwvc3VwPiZuYnNwOz0gMTQ1PFwvbGk+XHJcblx0PGxpPjE8c3VwPjI8XC9zdXA+Jm5ic3A7KyA0PHN1cD4yPFwvc3VwPiZuYnNwOysgNTxzdXA+MjxcL3N1cD4mbmJzcDs9IDQyPFwvbGk+XHJcblx0PGxpPjQ8c3VwPjI8XC9zdXA+Jm5ic3A7KyAyPHN1cD4yPFwvc3VwPiZuYnNwOz0gMjA8XC9saT5cclxuXHQ8bGk+MjxzdXA+MjxcL3N1cD4mbmJzcDsrIDA8c3VwPjI8XC9zdXA+Jm5ic3A7PSA0PFwvbGk+XHJcblx0PGxpPjQ8c3VwPjI8XC9zdXA+Jm5ic3A7PSAxNjxcL2xpPlxyXG5cdDxsaT4uLi4gYW5kIG5ldmVyIHRlcm1pbmF0ZXMmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BIFByaW1lIE51bWJlciBpcyBhbiBpbnRlZ2VyIGdyZWF0ZXIgdGhhbiAxIHRoYXQgY2FuIGJlIGRpdmlkZWQgb25seSBieSAxIGFuZCBpdHNlbGYuIEhlcmUgYXJlIHNvbWUgcHJpbWUgbnVtYmVyczogMiwgMywgNSwgNywgMTEsIDEzLCAxNywgMTksICZoZWxsaXA7Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgSGFwcHkgUHJpbWUgTnVtYmVyIGlzIGEgcHJpbWUgbnVtYmVyIHdoaWNoIGFsc28gc2F0aXNmaWVzIHRoZSBoYXBweSBudW1iZXIgY29uZGl0aW9uIHN1Y2ggYXMgNywgMTMsIDE5LCAmaGVsbGlwOyZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIHNob3cgYWxsIGhhcHB5IHByaW1lIG51bWJlcnMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIGEgZ2l2ZW4gbnVtYmVyIG4uICgxMCAmbGU7IG4gJmxlOyAxMDAwMDAwKSZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+QSBwb3NpdGl2ZSBudW1iZXIgbiBpcyB0aGUgb25seSBpbnB1dCBvZiB0aGUgcHJvZ3JhbS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgcHJvZ3JhbSBwcmludHMgYWxsIGhhcHB5IG51bWJlcnMgaW4gYXNjZW5kaW5nIG9yZGVyLCBvbmUgbnVtYmVyIGluIGEgbGluZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=