Introduction:
Welcome to Day 25 of the 30 Days of Code challenge! Today, we'll delve into the concept of running time, particularly time complexity. If you haven't already, check out the Tutorial tab for valuable learning materials and an instructional video.
The Challenge:
In today's task, we'll focus on determining whether a given number is prime or not. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Your goal is to implement a primality algorithm to determine and print whether a given number is prime.
Format & Sample:
The input consists of the following:
The first line contains an integer, t, the number of test cases.
The t subsequent lines each contain an integer, n, to be tested for primality.
The output should be whether each n is "Prime" or "Not prime" on a new line.
Input Format:
3
12
5
7
Output Format:
Not prime
Prime
Prime
Explanation:
Test Case 0: 12 is divisible by numbers other than 1 and itself (i.e., 2, 3, 4, 6), so we print "Not prime" on a new line.
Test Case 1: 5 is only divisible by 1 and itself, so we print "Prime" on a new line.
Test Case 2: 7 is only divisible by 1 and itself, so we print "Prime" on a new line.
Code Breakdown:
Reading Input:
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
Primality Check:
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t;
cin >> t;
while (t-- > 0) {
int n;
cin >> n;
// Implement primality check here
}
return 0;
}
Printing Output:
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t;
cin >> t;
while (t-- > 0) {
int n;
cin >> n;
// Implement primality check here
if (n < 2) {
cout << "Not prime" << endl;
continue;
}
bool isPrime = true;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
isPrime = false;
break;
}
}
cout << (isPrime ? "Prime" : "Not prime") << endl;
}
return 0;
}
Final Code:
#include <cmath>
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t-- > 0) {
int n;
cin >> n;
// Implement primality check here
if (n < 2) {
cout << "Not prime" << endl;
continue;
}
bool isPrime = true;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
isPrime = false;
break;
}
}
cout << (isPrime ? "Prime" : "Not prime") << endl;
}
return 0;
}
This concludes Day 25 of the 30 Days of Code challenge. You've successfully implemented a primality check for given numbers. Continue your coding journey!