Я решал загадку, где им требовалось найти самый большой Prime Factor составного числа, введенного пользователем. Я что-то придумал и попробовал, но ему не удается обнаружить самый большой простой фактор среди факторов составного числа.
Я добавляю свой код ниже, я был бы признателен, если бы кто-нибудь мог помочь мне здесь, чтобы обнаружить самый большой премьер-нет. среди факторов и распечатать его.
// Accept a composite number from user and print its largest prime factor. #include 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 0) b = i; else if(i==3) b = 3; } } } printf("%d\nLargest prime factor: %d\n", c, b); } Трюк состоит в том, чтобы найти наименьший простой множитель и делить на него составное число c , чтобы получить наибольший простой коэффициент.
Трюк состоит в том, чтобы найти наименьший коэффициент F (начиная с 2), где C / F является простым. Тогда C / F будет наибольшим простым множителем C.
Изменить: похоже, вы также хотите перечислить все факторы. Проблема заключается в том, что в вашем внутреннем цикле, который проверяет правильность, вы устанавливаете наибольшее простое число для чисел, которые делятся на что угодно. Другими словами, попробуйте что-то вроде этого:
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() в
Чтобы найти основную факторизацию, вы обычно найдете все факторы между 2 и sqrt (N). Вы разделите композит на каждый из них, чтобы получить остальные факторы. Затем recursion, чтобы найти основные факторы каждого из них.
Когда вы закончите, у вас будет список всех основных факторов. Получение самого большого элемента в списке должно быть довольно тривиальным.
В вашем внутреннем цикле вы устанавливаете b = i если существует число, которое не является фактором i . Вам нужно установить b = i если не существует числа, которое является фактором i .
(по «числу», я имею в виду «целое число от 2 до sqrt(i) », конечно)
Факторизация – classическая проблема теории чисел. Вы можете найти множество алгоритмов факторизации в учебниках по теории чисел. Некоторые из них доступны на wiki http://en.wikipedia.org/wiki/Integer_factorization
Привет, спасибо за входных друзей, я что-то разработал, и теперь программа печатает наибольший основной коэффициент составного числа при условии, что составной номер меньше 52, тогда как для более высоких диапазонов выше этого он не печатает правильный вывод , Я добавляю код, пожалуйста, посмотрите, могли бы вы, ребята, помочь мне
#include
void main () {int i, j, b = 2, c; printf (“\ nВведите составное число:”); scanf (“% d”, & c); 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);
}
В 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
То, что я сделал для проверки примитивности, – это аккуратная техника квадратного корня.