BL
U

8. Prime Check and Divisor Count

Easy

Problem Description

Given a positive integer NN, determine whether NN is a prime number and count the total number of its positive divisors.

Recall:

  • •A prime number is an integer strictly greater than 1 whose only divisors are 1 and itself.
  • •11 is not prime and has exactly 11 divisor.

Input Format

A single line containing a positive integer NN.

Output Format

  • •Line 1: true if NN is prime, otherwise false.
  • •Line 2: An integer representing the total count of positive divisors of NN.
Example 1:
Input:
7
Output:
true
2
Explanation: 7 is only divisible by 1 and 7 (2 divisors), so it is prime.
Example 2:
Input:
12
Output:
false
6
Explanation: The positive divisors of 12 are 1, 2, 3, 4, 6, 12 (6 divisors). Not prime.
Example 3:
Input:
1
Output:
false
1
Explanation: 1 has only 1 divisor and is not prime by definition.
Constraints:
  • 1 <= N <= 10^9
  • Time complexity target: O(sqrt(N))
  • Auxiliary space target: O(1)
Follow up:How would you quickly check primality for N up to 10^18 using Miller-Rabin?
1,180 Online