Простой делитель числа

Question

Простые делители числа 13195 - это 5, 7, 13 и 29. Каков самый большой делитель числа 600851475143, являющийся простым числом?

Не совсем понимаю проблему в своем алгоритме. По сути, мы должны найти корень из заданного числа, после чего сделать проверку на простоту этого делителя. Но в моём решении создается не простое число.

Результат: 486847 - не простое число

using System;
using System.Collections.Generic;

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            long number = 600851475143;

            int chislo = Convert.ToInt32(Math.Sqrt(number));

            int res = 0;

            List<int> lists = new List<int>();

            for(int i = 1; i < chislo; i++)
            {
                if(number % i == 0)
                {
                    lists.Add(i);
                }
            }

            for(int i = 0; i < lists.Count; i++)
            {
                for(int j = 2; j < lists.Count; j++)
                {
                    if(lists[i] % j != 0 && lists[i] > 1)
                    {
                        res = lists[i];
                    } 
                }
            }

            Console.WriteLine(res);
        }

    }
}

Answer 1

Просто оставлю это здесь. Решение не моё, нагуглил и немного причесал.

Добавил только от себя метод, проверяющий, действительно ли результат - простое число. Если делитель не найден, функция возвращает -1.

static void Main(string[] args)
{
    long number = 600851475143;
    long result = LargestPrimeDivisor(number);

    Console.WriteLine(result);
    Console.WriteLine(IsPrime(result));

    Console.ReadKey();
}

static long LargestPrimeDivisor(long number)
{
    if (number == 4)
        return 2;
    long result = -1;
    int counter = 0;

    for (long i = 2; i * i <= number && number != 1; i++)
    {
        while (number % i == 0)
        {
            number /= i;
            result = i;
        }
        if (result == i)
            counter++;
    }

    if (number != 1 && result != -1)
        return number;

    if (counter == 1)
        return -1;

    return result;
}

static bool IsPrime(long number)
{
    if (number < 2) 
        return false;
    for (long i = 2; i * i <= number; i++)
    {
        if (number % i == 0) 
            return false;
    }
    return true;
}

Вывод в консоль

6857
True

Вообще заданное число ровненько раскладывается на 4 простых множителя.

6857 * 1471 * 839 * 71 = 600851475143

БЛОГ НА HUSL

Простой делитель числа

Ответы (1 шт):