Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Check Prime

Easy
0/40
Average time to solve is 14m
profile
Contributed by
201 upvotes

Problem statement

A prime number is a positive integer that is divisible by exactly 2 integers, 1 and the number itself.


You are given a number 'n'.


Find out whether 'n' is prime or not.


Example :
Input: 'n' = 5

Output: YES

Explanation: 5 is only divisible by 1 and 5. 2, 3 and 4 do not divide 5.
Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line of a test case contains a single integer 'n'.


Output Format :
Print “YES” if the number 'n' is prime. Print “NO” otherwise.


Note :
You do not need to print anything; it has already been taken care of. Just implement the given function and return the boolean value true/false depending on whether 'n' is prime or not.
Sample Input 1:
5


Sample Output 1:
YES


Explanation of sample input 1 :
5 is only divisible by 1 and 5. 2, 3 and 4 do not divide 5.


Sample Input 2:
6


Sample Output 2:
NO


Explanation of sample input 2 :
6 is divisible by 1, 2, 3, and 6. Therefore it is not a prime number.
Numbers having more than two factors are known as composite numbers.


Sample Input 3:
1


Sample Output 3:
NO


Explanation of sample input 3 :
1 is divisible only by 1, having only one factor. Therefore it is not a prime number.
1 is neither a prime nor a composite number.


Expected time complexity :
The expected time complexity is O(sqrt('n')).


Constraints :
1 <= 'n' <= 10 ^ 9

Time limit: 1 second
Video Solution
Unlock at level 3
(75% EXP penalty)
Check Prime
All tags
Sort by
Search icon

Interview problems

Using C++ with utmost accuracy

 

bool isPrime(int n) {
  // Write your code here.

  int cnt = 0;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      cnt++;
      if ((n / i) != i) {
        cnt++;
      }
    }
  }
  if (cnt == 2)
    return true;
  else
    return false;
}

33 views
0 replies
0 upvotes

Interview problems

C++ Solution with explanation

•Better than 97.12%

•Runtime is 65 ms

•Time Complexity is O(sqrt(n))

bool isPrime(int n) {
    // Check if the number is less than or equal to 1; if so, it is not prime
    if (n <= 1) {
        return false; // 0 and 1 are not prime numbers
    }
    
    // Check if n is 2, which is the only even prime number
    if (n == 2) {
        return true; // 2 is prime
    }

    // If n is even and greater than 2, it cannot be prime
    if (n % 2 == 0) {
        return false; // Exclude all even numbers greater than 2
    }

    // Loop through odd numbers from 3 to the square root of n
    for (int i = 3; i * i <= n; i += 2) {
        // Check if i is a divisor of n
        if (n % i == 0) {
            return false; // If n is divisible by any odd number, it's not prime
        }
    }

    // If no divisors were found, n is prime
    return true; // n has no divisors other than 1 and itself
}
22 views
0 replies
1 upvote

Interview problems

better than 97.12%

bool isPrime(int n) {
    // Handle special cases
    if (n <= 1) return false;  // 0 and 1 are not prime
    if (n == 2) return true;   // 2 is the only even prime number
    if (n % 2 == 0) return false; // Other even numbers are not prime

    // Check for factors from 3 to sqrt(n), skipping even numbers
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return false; // Found a factor, so n is not prime
        }
    }
    return true; // No factors found, so n is prime
}
50 views
0 replies
0 upvotes

Interview problems

c++ code

bool isPrime(int n)
{
	if (n<2) return false;
	int counter = 0;
	for (int i=2;i*i<=n;i++){
		if(n%i==0){
			return false;
		}
	}
	return true;

}
48 views
0 replies
0 upvotes

Interview problems

c++ code

bool isPrime(int n)
{
	if(n<2) 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;
		}
	}
	reeturn true;

}
20 views
0 replies
0 upvotes

Interview problems

Its asking to return YES or NO from boolean return type

how it is supposed to be done  even after calling in main function and printing yes or no for true or false it is not accepting.

69 views
1 reply
11 upvotes

Interview problems

Optimal Solution

int count = 0;
    int sqrtN = sqrt(n);
    for (int i = 1; i <= sqrtN; ++i)
    {        
       if (n % i == 0) { 
           count++;
            if (i != (n/ i)) {
                count++;
            }
            cout<<count<<endl;
        }
    }
    if (count != 2)
    {
        return "NO";
    }

    return "YES";
277 views
0 replies
0 upvotes

Interview problems

Check Prime

bool isPrime(int n)

{

    // Write your code here.

    int cnt=0;

    for(int i=1;i<=n;i++){

        if(n%i==0){

            cnt=cnt+1;

        }

    }

    if(cnt==2){

        return true;

    }

    else{

        return false;

    }

}

237 views
0 replies
0 upvotes

Interview problems

n1=5 output will be =NO

compiled the code output for n1=5 will be NO

85 views
0 replies
2 upvotes

Interview problems

98% better solution

bool isPrime(int n)

{

     if (n <= 1) {

        return false; 

}

 for (int i = 2; i * i <= n; ++i) {

        if (n % i == 0) {

          return false;

        }

 }

 

 return true;

}

beginners

programming

346 views
1 reply
2 upvotes
Full screen
Console