This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging

describe

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer m is a divisor of n if there exists an integer k such that n = k * m.

Example 1:

Input: n = 2
Output: false
Explantion: 2 has only two divisors: 1 and 2.
Copy the code

Example 2:

Input: n = 4
Output: true
Explantion: 4 has three divisors: 1, 2, and 4.
Copy the code

Note:

1 <= n <= 10^4
Copy the code

parsing

If n is given a positive integer, determine whether n has exactly three positive integer divisor.

Returns True because the divisor of 4 is exactly 1, 2, and 4Copy the code

And we can see from the problem that, in fact, after giving n, except for 1, which has only one divisor, which is itself, every other number has at least two divisor, which is 1 and itself, which is n, so our goal is to determine whether there is only one other divisor between 1 and n.

  • If n<=3, return False
  • Since the largest divisor of a number n is n//2, initialize mid= n//2 and initialize a counter count to record the number of divisor numbers that occur
  • If count>1, return False. If count>1, return False. If count>1, return False
  • Return True if count is 1, plus 1 and n itself, which means there are exactly three divisor, or False otherwise.

answer

class Solution(object):
    def isThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n<=3:return False
        mid = n//2
        count = 0
        for i in range(2, mid+1):
            if n%i==0:
                count += 1
            if count>1:
                return False
        return count==1
        	      
		
Copy the code

The results

The linked list for each node in the linked list: 10000 ms Submissions to the linked list for Three DivisorsCopy the code

parsing

In addition, digging deep into the first idea above, we find that only the square of a prime number can be meaningful, because the square of a prime number must only have three divisor 1, the prime number itself, and the square of a prime number. The problem specifies that n is at most 10,000. So only if n is in [4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409] returns True, otherwise returns False.

answer

class Solution(object):
    def isThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n in [4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409]
Copy the code

The results

Runtime: 10 ms, the linked list for each node in the linked list. Submissions in the linked list for Three DivisorsCopy the code

Link: leetcode.com/problems/th…

Your support is my greatest motivation