どーも、みつおです。
この問題は手計算でできるのだろうか。
問題
3195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
出典：Problem 3
解答
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
using System; namespace Problem3 { class Program { static void Main(string[] args) { Console.WriteLine(Solve()); Console.ReadLine(); } private static long Solve() { long ret = 0; long num = 600851475143; //素因数分解した場合の最大値(平方根)を求める long root = (long)Math.Sqrt(num); //最大値から順に減少させていく for(long i = root; 0 < i; i--) { //割り切れるか判定 if(num % i == 0) { //素数か判定 if(IsSosu(i)) { ret = i; break; } } } return ret; } private static bool IsSosu(long no) { bool ret = true; //数値が2未満なら素数じゃない、2なら素数 if (no < 2) return false; else if (no == 2) return true; //数値が2で割り切れるなら素数じゃない if (no % 2 == 0) return false; //奇数でループ for (int i = 3; i < no; i += 2) { //割り切れるので素数じゃない if (no % i == 0) return false; } return ret; } } } |
出力
6857
コメントを残す