Day 25: Running Time and Complexity
Objective
Hey CodingHumans today we're learning about running time!
By running time, we mean to evaluate the performance of an algorithm in terms of input size (we don't measure the actual running time). We calculate, how the time (or space) taken by an algorithm increases with the input size
Problem
Task
A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. Given a number, n, determine and print whether it's Prime or Not prime.
Note: If possible, try to come up with a O( √ n) primality algorithm, or see what sort of optimizations you come up with for an O(n) algorithm. Be sure to check out the Editorial after submitting your code!
Input Style
The first line contains an integer, T, the number of test cases.
Each of the T subsequent lines contains an integer, n , to be tested for primality.
Constraints
1<= T<= 30
1<= n <= 2 X 10^9
Output Style
For each test case, print whether n is Prime or Not Prime on a new line.
Sample Input
3
12
5
7
Sample Output
Not prime
Prime
Prime
Explanation
Test Case 0:n=12 .
12 is divisible by numbers other than 1 and itself (i.e.:2 ,3 ,6 ), so we print Not Prime on a new line.
Test Case 1: .
5 is only divisible 1 and itself, so we print Prime on a new line.
Test Case 2: .
7 is only divisible 1 and itself, so we print Prime on a new line.
Recommended: Please try your approach on your integrated development environment (IDE) first, before moving on to the solution.
Few words from CodingHumans : Don't Just copy paste the solution, try to analyze the problem and solve it without looking by taking the the solution as a hint or a reference . Your understanding of the solution matters.
HAVE A GOOD DAY 😁
Solution
( Java )
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static void prime(int n)
{
boolean flag=false;
for(int i=2;i<=Math.sqrt(n);i++)
{
if(n%i==0)
{
flag=true;
break;
}
}
if(n==1){
System.out.println("Not prime");
}
else if(!flag){
System.out.println("Prime");
}
else{
System.out.println("Not prime");
}
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t--!=0)
{
int n=sc.nextInt();
prime(n);
}
}
}
If you have any doubts regarding this problem or need the solution in other programming languages then leave a comment down below .
