CODEWITHSUNDEEP
cprimes
janniks
janniks

Reputation: 3180

C error finding largest prime factor

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(unsigned long long x) {
    if (x % 2 == 0)
        return false;
    for (unsigned long long i = 3; i < sqrt(x); x += 2) {
        if (x % i == 0)
            return false;
    }
    return true;
}

int main(int argc, char const *argv[]) {
    unsigned long long largest, number = 13195;

    for (unsigned long long i = 2; i < number; i++) {
        if (isPrime(i) && number % i == 0) {
            largest = i;
        }
    }

    printf("Largest : %llu\n", largest);

    return EXIT_SUCCESS;
}

Is the Prime number function working? If I remove the sqrt() in the for-loop, I get an endresult of 0, which is strange...

I'm getting an output of 7, but the largest prime factor should be 29 Why is this happening?

Upvotes: 0

Views: 126

Answers (2)

chux
chux

Reputation: 154146

Code error, change

// for (unsigned long long i = 3; i < sqrt(x); x += 2) {
for (unsigned long long i = 3; i < sqrt(x); i += 2) {
//                                          ^

For fun, isPrime() simplification: (works for long long)

bool isPrime(long long x) {
  if (x % 2 == 0)
    return x == 2;
  long long i = 1;
  lldiv_t qr;
  do {
    i += 2;
    qr = lldiv(x, i);
    if (qr.rem == 0) {
      return false;
    }
  } while (i < qr.quot);
  return true;
}

Upvotes: 1

user529758
user529758

Reputation:

Here you have a typo:

x += 2

should be

i += 2

This makes your isPrime(29) return false.

By the way, why bother? A much simpler solution would be to just factorize the number:

unsigned long long number = 13195;
unsigned long long i, max = 2;
unsigned long long orig = number;

for (i = 2; i <= orig; i++) {
    while (number % i == 0) {
        number /= i;
        max = i;
    }
}

printf("largest: %llu\n", max);

Upvotes: 5

Related Questions