program compiles but does not executes

Question

I compiled the program but when i gave input=600851475143 no result comes.The program is to find the largest prime factor( The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?) What is wrong?

#include<stdio.h>


int isprime(unsigned long  n){
    unsigned long i;
    for(i=2;i<n;i++){
        if((n%i)==0){
            return 0;
        }
    }
    return 1;
}

int main(){
    unsigned long n,i,lpf;
    scanf("%ld",&n);
    for(i=2;i<n;i++){
        if(n%i==0){
            if(isprime(i)==1){
            lpf=i;}
        }
    }
    printf("%ld",lpf);
    return 0;
}

For big number it would take quite a time to compute and also `%ld` isn't a correct specifier for `unsigned long`. — ameyCU, Sep 30 '16 at 18:38
Your `unsigned long` would need to be 64-bit. Is it? As others state, the number of calculations is simply enormous, so the program will run for *years* probably. You need a smarter way of solving the problem. My pennyworth is since you want to find the *largest* prime factor, work from top down and not bottom up. Oh, and don't check the even numbers or divisors. — Weather Vane, Sep 30 '16 at 19:25

galfisher · Answer 1 · 2016-09-30T18:47:32.450

You have a for loop that runs roughly the times the number you entered, i goes from 2 to n-1. In that for loop you call a function, that runs roughly i times, that's the same i in the loop. That means that your program does around n^2 math calculations where n is your input. If you enter a 12 digit number, n^2 is the size of a 24 digit number, and for a program it will take a lot of time to do a 10^24 calculations. So your program does run, it just calculates.

deamentiaemundi · Answer 2 · 2016-10-01T01:22:42.920

As the others already said: you don't need to walk the whole path. It is sufficient to go up to the square root of n, You can also reduce the value of n itself every time you found a factor.

A slightly faster way, although of the same time complexity as the naive version, is to use a wheel. The wheel used here are the distances between the 11-rough numbers (plus the primes before and an offset for the next rounds).

All together:

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

#define ISPRIME(x) isprime(x)
//#define ISPRIME(x) isprime_wheel(x)

static int wheel[] = {
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2,
4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 2,
4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6,
2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12,
2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2,
6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8,
4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2, 10,
2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4,
6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4,
2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4,
6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4,
6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10,
2, 10, 2, 4, 2, 4, 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6,
4, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6,
4, 2, 10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12,
4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4,
2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 2, 4,
2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4,
8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12
};

int isprime_wheel(unsigned long n)
{
  unsigned long isqrt = (unsigned long) (floor(sqrt(n)) + 1);
  unsigned long start = 5, factor = 2;
  int wlen = sizeof(wheel) / sizeof(int);
  int next = 0;
  if(n == 2){
    return 1;
  }
  if ((n & 1) == 0) {
    return 0;
  }
  if (isqrt * isqrt == n) {
    return 0;
  }
  while (factor < isqrt) {
    if (n % factor == 0) {
      return 0;
    }
    factor += (unsigned long) wheel[next];
    next++;
    if (next == wlen) {
      next = start;
    }
  }

  return 1;
}

unsigned long primefactors(unsigned long n)
{
  unsigned long start = 5, factor = 2;
  unsigned long biggest = 0;
  int wlen = sizeof(wheel) / sizeof(int);
  int next = 0;
  if (n == 1) {
    return 0;
  }
  if (n == 2 || n == 3) {
    return n;
  }

  while (factor <= n) {
    while (n % factor == 0) {
      biggest = factor;
      n /= factor;
    }
    factor += (unsigned long) wheel[next];
    next++;
    if (next == wlen) {
      next = start;
    }
  }
  if (n > 1 && biggest == 0) {
    return n;
  }

  return biggest;
}



int isprime(unsigned long n)
{
  unsigned long i;
  unsigned long isqrt = (unsigned long) floor(sqrt(n)) + 1;

  for (i = 2; i < isqrt; i++) {
    if ((n % i) == 0) {
      return 0;
    }
  }
  return 1;
}

#include <time.h>
int main()
{
  unsigned long n, i, lpf = 0, wheelfactor = 0;
  clock_t start,stop;

  if(scanf("%lu", &n) != 1){
     fprintf(stderr,"Must be a positive, small integer \n");
     exit(EXIT_FAILURE);
  }

  start = clock();
  wheelfactor = primefactors(n);
  stop = clock();
  printf("WHEEL Time %.10f seconds\n", (double) (stop - start) / CLOCKS_PER_SEC);
  printf("WHEEL %lu\n",wheelfactor );

  start = clock();
  if (n == 1) {
    puts("0");
    goto END;
  }
  if (n == 2 || ISPRIME(n) == 1) {
    printf("NAIVE %lu (n is prime, next print must show 0)\n", n);
    goto END;
  }
  for (i = 2; i < n / 2 + 1; i++) {
    if (ISPRIME(i) == 1 && n % i == 0) {
      //printf("PRIME %lu\n", i);
      lpf = i;
      n /= i;
      // n might be down to 2 and isprime(2) returns true
      // but  only odd primes are allowed at this point
      if (ISPRIME(n) == 1 && n > lpf) {
        //printf("ISPRIME %lu\n", n);
        lpf = n;
      }
    }
  }
END:
  stop = clock();

  printf("NAIVE Time %.10f seconds\n", (double) (stop - start) / CLOCKS_PER_SEC);
  printf("NAIVE %lu\n", lpf);
  return 0;
}

You might try it with some large composite like e.g.: 11529215046068460 to see the difference in runtime, or 1152921123 which is a bit more extreme and needs a lot of patience--it might need a couple of minutes.

@cdlane yepp, my bad, the outer loop must be `n/2 +1` of course, we're searching for factors here and not for primes and if one of the factors is `2` ... — deamentiaemundi, Sep 30 '16 at 21:29
@cdlane primes have no prime factors. If it is wanted, just check if it is a prime in the first place, before you enter the outer loop. But it is no problem for me to add it. — deamentiaemundi, Sep 30 '16 at 22:01
Can you provide a link to a site that explains that "primes have no prime factors" as I keep running into statements like, "all integers n > 1 have prime factors" and "When n is a prime number, the prime factorization is just n itself". — cdlane, Sep 30 '16 at 22:10
@cdlane found more bugs, hope I could fix them all, please check — deamentiaemundi, Sep 30 '16 at 22:33
@cdlane added an algorithm with a wheel and while doing that I foun dout that the wheel in my JavaScript implementation seems to have been corrupted (ar simple a C&P error), it gave wrong results. Sometimes. So thanks for making me fix a bug in one of my published programs! — deamentiaemundi, Oct 01 '16 at 01:16

score 0 · Answer 3 · edited May 23 '17 at 10:27

Earlier, I noted that my original solution:

still takes too long for 600851475143 so it's time to look for a completely different algorithm

A search of SO turns up efficient ways of finding the largest prime factor of a number.

Here's a simple and fast solution based @under5hell's answer on that page:

#include <stdio.h>
#include <assert.h>

int main()
{
    unsigned long long number;

    assert(sizeof(number) * 8 >= 64); // make sure we've enough bits

    scanf("%llu", &number);

    for (unsigned long long divisor = 2; divisor < number; divisor++) {
        if (number % divisor == 0) {
            number /= divisor--; // decrement to remove multiples
        }
    }

    printf("%llu\n", number);

    return 0;
}

Which can find the largest prime factor of 600851475143 in a fraction of a second:

OUTPUT

> ./a.out
600851475143
6857
>

Moral of the story seems to be search SO before you query SO!

600851475143 requires 41 bits. The `unsigned long` type is only required to provide 32; as of C99, C provides `[unsigned] long long` which can hold this value. — Kaz, Oct 01 '16 at 00:17
Yes, @Kaz, I was working on that issue when I saw your comment. I've upped it long long and made a 64 bit assertion though I'm sure I really should be using uint64_t or some such. — cdlane, Oct 01 '16 at 00:25

program compiles but does not executes

3 Answers3