2

Простые делители числа 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);
        }

    }
}

3
  • половина делителей теряется, потому что добавляется только один из них
    – Grundy
    28 июл 2021 в 8:41
  • 3
    По сути, мы должны найти корень из заданного числа, после чего сделать проверку на простоту этого делителя - нет, конечно. По вашему, если число не является квадратом просто числа, то у него и нет простых делителей? 28 июл 2021 в 9:22
  • Просто раскладывайте на простые множители, стандартно по возрастанию множителя. Последний и будет решением.
    – Akina
    28 июл 2021 в 9:42

1 ответ 1

2

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

Добавил только от себя метод, проверяющий, действительно ли результат - простое число. Если делитель не найден, функция возвращает -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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.