terminate - My C code doesn't output anything, or end running -
i'm trying answer question:
the prime factors of 13195 5, 7, 13 , 29.
what largest prime factor of number 600851475143 ?
here code:
#include <stdio.h> int isprime(long long num) { (long long k = 1; k < num; k++) { if (num%k == 0) return 0; } return 1; } long long num = 600851475143; int main(void) { long long prime_factor = 0; (long long j = 2; j < num; j++) { if (num % j == 0 && isprime(j) == 1) prime_factor = j; } printf("%lli\n", prime_factor); }
but reason doesn't print anything, or end. causing this?
that's terribly inefficient way of finding prime factors of number.
to find prime factors, should:
- create static list of primes less or equal (number / 2).
- iterate on each element in list of primes , see if each 1 can evenly divide number.
- divide original number prime, , check last number again.
why? smallest prime 2. if number isn't first prime can divide number > 2 3.
every number can uniquely identified prime factors. called fundamental theorem of arithmetic. means there 1 way represent e.g. 15 product of primes, in case { 3, 5 }.
however prime can divide number more once. example, 49 product of 2 primes { 7, 7 }. dividing original number 1 of factors makes subsequent divisions quicker. , can logically stop checking when number == 1.