Finding Sphenic Numbers - Not Producing Expected Output

Question

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

bool PrimeNum (int n) {
    if (n<=1) {
        return false;
    }

    for (int i = 2; i <= sqrt(n); i++) {
        if (n%i == 0) {
            return false;
        } 
    }
    return true;
}

bool findSphenic(int num, int count) {
    if (num == 1 && count == 3) {
        return true;
    } 
    if (count > 3 || num == 1) {
        return false;
    }

    for (int j = num - 1; j > 1; j--) {
        if (num % j == 0 && PrimeNum(j)) {
            if (findSphenic(num / j, count + 1)) {
                return true;
            }
        }
    }
    return false;
}


void display (int n) {
    for (int k = 1; k<=n; k++) {
        if (findSphenic(k, 0)) {
            printf("%d\n", k);
        }
    }
}

int main() {
    int num;
    printf("Type in a number: ");
    scanf("%d", &num);
    display(num);
    return 0;
}

I want it to print out any number in the range from 1 to n that is sphenic num but after fixing bool Primenum and bool findSphenic several times, it still doesn't give me the answer I want. It just prints out "Type in a number" and after I give a number nothing happens.

Example:

Type in a number: 45

Nothing happens. It supposes to print 30 since it's a sphenic num.

Thanks in advance.

Answer 1

Here is a version of your function which works. As you can see, the loop counts up instead of down.

bool findSphenic(int num, int count) {
    if (num == 1 && count == 3) {
        return true;
    } 
    if (count > 3 || num == 1) {
        return false;
    }
    for (int j = 1; j <= num; j++) {
        if (num % j == 0 && PrimeNum(j)) {
            if ((num/j) % j == 0) return false;
            if (findSphenic(num / j, count + 1)) {
                return true;
            }
        }
    }
    return false;
}

Notice that it also checks that there can not be repeated factors. I don't think you can easily do that counting down. On my old laptop (Core i5), it finds (without printing) the 19919 Sphenic numbers below 100,000 in 10.7 seconds. Though the following is still quite naive, it takes 0.18 seconds to do the same, illustrating that efficient code does not always have to be complicated.

void myfindSphenic(int num) {
  // Print all Sphenic integers up to num
  int i, j, k, count, numfound;
  numfound = 0;
  for (i=30; i<=num; i++) {
    count = 0;
    k = i;
    for (j=2; k > 1 && count<=2; j++) {
      if (k % j == 0) {
        k /= j;
        if (k % j == 0) break;
        count++;
      }
      if ((count == 0) && (j>num/(j*j))) break;
      if ((count == 1) && (j>(k/j))) break;
    }
    if ((count == 3) && (k == 1)) {
      //printf("%i  ", i);
      numfound++;
    }
  }
  printf("Found %i Sphenic numbers not greater than %i\n", numfound, num);
}