C # крупнейший простой фактор с модулем? - PullRequest
Новая
       32

C # крупнейший простой фактор с модулем?

0 голосов
/ 07 ноября 2010

Мне было интересно, можно ли найти наибольший простой множитель числа с помощью модуля в C #.Другими словами, если i % x == 0, то мы можем разорвать цикл for или что-то в этом роде, где x равно всем натуральным числам ниже нашего значения i.

Как бы я указалall natural numbers below our i value равно нашей переменной x?Становится немного утомительно выписывать условные выражения для каждого целого числа, если вы знаете, о чем я говорю.

Кстати, я уверен, что есть далеко более простой способ сделатьэто в C #, поэтому, пожалуйста, дайте мне знать об этом, если у вас есть идея, но я также хотел бы попытаться решить ее таким образом, просто чтобы посмотреть, смогу ли я сделать это со своими знаниями для начинающих.

Вот мой текущий код, если вы хотите увидеть, что у меня есть: 

static void Main()
{
    int largestPrimeFactor = 0;

    for (long i = 98739853; i <= 98739853; i--)
    {
        if (true)
        {
            largestPrimeFactor += (int) i;
            break;
        }
    }

    Console.WriteLine(largestPrimeFactor);
    Console.ReadLine();
}

Ответы [ 3 ]

6 голосов
/ 07 ноября 2010

Если бы я делал это, используя цикл и модули, я бы сделал: 

long number = 98739853;
long biggestdiv = number;

while(number%2==0) //get rid of even numbers
    number/=2;

long divisor = 3;

if(number!=1)
while(divisor!=number)
{
    while(number%divisor==0)
    {
        number/=divisor;
        biggestdiv = divisor;
    }

    divisor+=2;
}

В конце, biggestdiv будет наибольшим простым множителем.

Примечание: Этот коднаписано прямо в браузере.Я не пытался скомпилировать или запустить его.Это только для того, чтобы показать мою концепцию.Там могут быть ошибки алгоритма.Это они, дайте мне знать.Я осознаю тот факт, что он вообще не оптимизирован (я думаю, что для этого лучше всего подходит Sieve).

РЕДАКТИРОВАТЬ:
исправлено: предыдущий код возвращал 1, когдаnumber были простыми.
исправлено: предыдущий код заканчивался циклом, приводя к переполнению divisor, где number было степенью 2

3 голосов
/ 07 ноября 2010

Ох, это звучит как забавное использование для блоков итераторов.Не передавайте это своему профессору: 

private static List<int> primes = new List<int>() {2};
public static IEnumerable<int> Primes()
{
    int p;
    foreach(int i in primes) {p = i; yield return p;}

    while (p < int.MaxValue)
    {
       p++;

       if (!primes.Any(i => p % i ==0))
       {
           primes.Add(p);
           yield return p;
       }
    }          
}

public int LargestPrimeFactor(int n)
{
     return Primes.TakeWhile(p => p <= Math.Sqrt(n)).Where(p => n % p == 0).Last();
}
1 голос
/ 07 ноября 2010

Я не совсем понимаю, в чем ваш вопрос: возможно, вам нужен цикл по числам? Однако с вашим кодом есть две явные проблемы:

  • Ваш цикл for имеет одинаковое значение остановки и окончания. Т.е. он будет запускаться один раз и только один раз

  • У вас есть перерыв до самой большой суммы PrimeFactor. Эта сумма НИКОГДА не будет выполняться, потому что break остановит цикл for (и, следовательно, выполнение этого блока). Компилятор должен предупредить, что эта сумма недоступна.

...