どーも、みつおです。
この問題は手計算でできるのだろうか。
問題
3195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
出典:Problem 3
解答
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
コメント