Given a positive integer value N. The task is to find how many numbers less than or equal to N have numbers of divisors exactly equal to 3 I have tried putting some fixes didn't worked any quick fixes or some detailed explanation for the issue will be great support. the code breaks at 625 that is it is taking 25 as prime. the code works well with just one extra count till 15624. the code then again breaks at 15625 with two extra counts. I have tried a fix for 625 but it does break ahead. I don't get it what's wrong with the code.

class Solution {
    public int exactly3Divisors(int N) {
        int count = 0;
        int leakCnt = 25;
        for (int i = 2; i * i <= N; i  ) {
            if (isPrime(i)) {
                if (i % leakCnt != 0)
                    count  ;
                else {
                    leakCnt *= 25;
                }
            }
        }
        return count;
    }
        static boolean isPrime(int N) {
            if (N == 1)
                return false;
            if (N == 2 || N == 3)
                return true;
            if (N % 2 == 0 || N % 3 == 0)
                return false;
            for (int i = 5; i * i < N; i  = 6) {
                if (N % i == 0 || N % (i   2) == 0)
                    return false;
            }
            return true;
        }
    }
        

CodePudding user response：

All composite numbers except perfect squares have at least four divisors.  For N they would be 1,  k,  j, and N.  Primes, P,  only have 2 divisors, 1 and P. But perfect squares have only three divisors as long as the square root is prime.

Examples are:
1, 3, 9
1, 5, 25
1, 11, 121

int n = 2010;
int count = exactly3Divisors(2010);
System.out.printf("For N = %d, there are %d numbers of only 3 divisors.",
      n, count);

• iterate of all perfect squares less than n
• Then check to see if the square root is prime and bump the count accordingly.

public static int exactly3Divisors(int n) {
    int count = 0;
    for (int i = 1; i*i <= n; i  ) {   
        if (isPrime(i)) {
            count  ;
        }
    }
    return count;
}

prints

For N = 2010, there are 14 numbers of only 3 divisors.

If you are not including 1 as a divisor then you need to find the numbers that have only two primes as divisors. This requires a version of isPrimes that memoizes previously computed primes. More on that later.

Here is the new exactly3Divisors method.

• iterate from 2 to n ignoring any number that is a prime.
• for each iterated number determine:
  • if it is divisible by a prime
  • if the quotient from that division is a prime (to avoid duplicate counts, make certain that the the current prime is > than the quotient.
  • if, the above succeeds increment the count.

public static int exactly3Divisors2(int n) {
    int count = 0;
    for (int i = 2; i <= n; i  ) {
        if (isPrime(i)) { 
            continue;
        }
        for (int p : primes) {
            int quotient = i / p;
            if (p <= quotient) {
                continue;
            }
            if (i % p == 0 && isPrime(quotient)) {
                count  ;
            }
        }
    }
    return count;
}

Here is the isPrime method

• store the primes in a LinkedHashSet to maintain the order and quick reference. The primes will always be in sorted order.
• if the number under test is <= last prime, then simply return true or false based on its presence in the set.
• Iterate thru the primes to see if any divide the current number and if so, return false.
• once the product of the current prime exceeds the number under test, add that number to the set of primes, assign numb to lastPrime, and return true;

static LinkedHashSet<Integer> primes = new LinkedHashSet<>(Set.of(2));
static int lastPrime = 2;
public static boolean isPrime(int numb) {
    if (numb > lastPrime) {
        for (int prime : primes) {
            if (numb % prime == 0) {
                return false;
            }
            if (prime * prime >= numb) {
                primes.add(numb);
                lastPrime = numb;
                return true;
            }
        }
        
    }
    return primes.contains(numb);
}

CodePudding user response：

As you mentioned in your question, there appears to be an issue with your isPrime method, since it's taking 25 as a prime number. I managed to fix it up a bit, by just doing a loop similar to what you did, but hopefully missing the gaps yours may have left:

public static boolean isPrime(int N) {
    if (N == 1)
        return false;
    if (N == 2 || N == 3)
        return true;
    for (int i = 2; i <= Math.sqrt(N); i  )
        if (N % i == 0)
            return false;
    return true;
}

Additionally, your exactly3Divisors method does not need some magic number for leaking numbers. If you ever have to do that, it probably means your logic is faulty somewhere. Since we already diagnosed that there was an issue with isPrime, it turns out that pretty much removed the need for any other variables than count:

public static int exactly3Divisors(int N) {
    int count = 0;
    for (int i = 2; i * i <= N; i  ) {
        if (isPrime(i)) {
            count  ;
        }
    }
    return count;
}

This should give you the correct answer. Running exactly3Divisors(625) should give you 9!