Algorithm
Problem Name: 30 days of code -
Objective
Today we will learn about running time, also known as time complexity. Check out the Tutorial tab for learning materials and an instructional video.
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 is Prime or Not prime.
Input Format
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 * 109
Output Format
Sample Input
3
12
5
7
Sample Output
Not prime
Prime
Prime
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int T;
long int n[T];
scanf("%d",&T);
for(int i = 0; i < T; i++){
scanf("%ld",&n[i]);
int flag=0;
for(long int j=sqrt(n[i]);j > 1; j--){
if(n[i]%j==0){
flag=1;
break;
}
}
if(flag){
printf("Not prime\n");
}else
if(n[i]==1){
printf("Not prime\n");
}else{
printf("Prime\n");
}
}
return 0;
}
Copy The Code &
Try With Live Editor
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cmath>
#include <iostream>
using namespace std;
bool isPrime(int n) {
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0) return false;
return true;
}
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int n;
cin >> n;
if (n >= 2 && isPrime(n)) cout << "Prime" << endl;
else cout << "Not prime" << endl;
}
}
Copy The Code &
Try With Live Editor
#3 Code Example with C# Programming
Code -
C# Programming
using System;
class Solution
{
public static bool isPrime(int n)
{
for (int i = 2; i <= Math.Sqrt(n); i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
static void Main(String[] args)
{
var T = int.Parse(Console.ReadLine());
for (int i = 0; i < T; i++)
{
int n = int.Parse(Console.ReadLine());
if (n >= 2 && isPrime(n)) Console.WriteLine("Prime");
else Console.WriteLine("Not prime");
}
}
}
Copy The Code &
Try With Live Editor
#4 Code Example with Golang Programming
Code -
Golang Programming
package main
import (
"fmt"
"math"
)
func checkPrime(num float64) string {
var i int
if num == 1 || (num != 2 && int(num)%2 == 0) {
return "Not prime"
}
for i = 3; i <= int(math.Sqrt(num)); i += 2 {
if int(num)%i == 0 {
return "Not prime"
}
}
return "Prime"
}
func main() {
var t int
fmt.Scan(&t)
s := make([]float64, t)
for k := range s {
fmt.Scan(&s[k])
}
for _, v := range s {
fmt.Println(checkPrime(v))
}
}
Copy The Code &
Try With Live Editor
#5 Code Example with Java Programming
Code -
Java Programming
import java.util.Scanner;
public class Solution {
public static boolean isPrime(int n) {
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int i = 0; i < T; i++) {
int n = in.nextInt();
if (n >= 2 && isPrime(n))
System.out.println("Prime");
else System.out.println("Not prime");
}
in.close();
}
}
Copy The Code &
Try With Live Editor
#6 Code Example with Javascript Programming
Code -
Javascript Programming
function processData(input) {
var arr = input.split('\n');
for (var i = 1; i < arr.length; i++){
var n = arr[i];
if(isPrime(n)){
console.log("Prime");
} else {
console.log("Not prime");
}
}
}
function isPrime(n){
if (n <= 1) {
return false;
}
if (n <= 3) {
return true;
}
// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0){
return false;
}
for (var index=5; index*index<=n; index=index+6){
if (n%index == 0 || n%(index+2) == 0) {
return false;
}
}
return true;
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
Copy The Code &
Try With Live Editor
#7 Code Example with Python Programming
Code -
Python Programming
from math import sqrt
T = int(input())
def isPrime(n):
for i in range(2, int(sqrt(n) + 1)):
if n % i is 0:
return False
return True
for _ in range(T):
n = int(input())
if n >= 2 and isPrime(n):
print("Prime")
else:
print("Not prime")
Copy The Code &
Try With Live Editor