Печать наибольшего простого множителя составного числа в C - PullRequest
Новая
       43

Печать наибольшего простого множителя составного числа в C

1 голос
/ 12 августа 2010

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

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

// Accept a composite number from user and print its largest prime factor.

#include<stdio.h>
void main()
{
    int i,j,b=2,c;
    printf("\nEnter a composite number: ");
    scanf("%d", &c);
    printf("Factors: ");

    for(i=1; i<=c/2; i++)
    {
        if(c%i==0)
        {
            printf("%d ", i);
            for(j=2; j<=i/2; j++) //since a numbr cand be divisible by a number greated than its half
            {               if(i%j > 0) 
                    b = i;
                else if(i==3)
                    b = 3;
            }
        }
    }
    printf("%d\nLargest prime factor: %d\n", c, b);
}

Ответы [ 6 ]

3 голосов
/ 12 августа 2010

Хитрость в том, чтобы найти наименьший простой множитель и разделить на него составное число c, чтобы получить самый большой простой фактор.

Хитрость заключается в том, чтобы найти наименьший фактор F (начиная с 2), где C / F - простое число. Тогда C / F будет наибольшим простым множителем C.

Редактировать: Похоже, вы также хотите перечислить все факторы. Проблема в том, что в вашем внутреннем цикле, который проверяет простоту, вы устанавливаете самое большое простое число на i для чисел, которые делятся на что угодно. Другими словами, попробуйте что-то вроде этого: 

is_prime = true;

for (j = 2; j <= x / 2; j++) {
    if (i % j == 0)
        is_prime = false;
}

if (is_prime)
    largest_prime = x;

Обратите внимание, что на самом деле вы можете остановиться раньше, чем x, деленное на 2. Вы можете остановиться на квадратном корне из x. Тем не менее, функция sqrt() в <math.h> немного сложна в вашем случае, потому что она работает с числами с плавающей запятой, а не с целыми числами.

1 голос
/ 12 августа 2010

Чтобы найти простую факторизацию, вы обычно находите все факторы от 2 до sqrt (N).Вы бы поделили композит на каждый из них, чтобы получить остальные факторы.Затем вернитесь, чтобы найти главные факторы каждого из них.

Когда вы закончите, у вас будет список всех основных факторов.Получение самого большого элемента в списке должно быть довольно тривиальным.

1 голос
/ 12 августа 2010

В вашем внутреннем цикле вы устанавливаете b = i, если существует , существует ли число, которое не с коэффициентом i.Вам нужно установить b = i, если не существует число, которое равно с коэффициентом i.

(под "числом" я имею в виду«целое число от 2 до sqrt(i)», конечно)

0 голосов
/ 17 мая 2012

В Python, что-то вроде этого будет делать: 

import math
import itertools

# largest prime factor of a composite number
def primality(num):
    for i in range(2,int(math.sqrt(num))+1):
        if num%i ==0:
             return 0
    return 1

if __name__ == '__main__':
    number = 600851475143
    for i in itertools.count(2,1):
            if number%i == 0:
                if number%10 in [7,9,1,3] and primality(number/i):
                    print number/i
                    break

Что я сделал, чтобы проверить первичность, так это метод аккуратного квадратного корня.

0 голосов
/ 12 августа 2010

Эй, спасибо за вводимые друзья, я кое-что разработал, и теперь программа выводит наибольший простой множитель составного числа, при условии, что составное число меньше 52, а для более высоких диапазонов оно не печатается. правильный вывод. Я добавляю код, пожалуйста, посмотрите, если вы, ребята, могли бы помочь мне вокруг 

#include<stdio.h>

void main () { int i, j, b = 2, c; printf ("\ nВведите составное число:"); scanf ("% d" и т. д.); printf ("Факторы:"); 

for(i=1; i<=c/2; i++)
{
    if(c%i==0)
    {
        printf("%d ", i);
        for(j=1; j<=i; j++) //since a numbr cand be divisible by a number greated than its half
        {               if(i%j > 0)
                b = i; //b stores the largest prime factor
            if(b%3==0)
                b = 3;
                else if(b%2==0)
                b=2;
              else if(b%5==0)
                b=5;
                }
    }
}


printf("%d\nLargest prime factor: %d\n", c, b);

}

0 голосов
/ 12 августа 2010

Факторизация - это классическая проблема теории чисел.Вы можете найти много алгоритмов факторизации в учебниках по теории чисел.Некоторые из них доступны на вики http://en.wikipedia.org/wiki/Integer_factorization

...