1403: Prime Pairs
Time Limit: 1000 ms Memory Limit: 65536 KB
Problem Description: Two prime numbers that differ by 2 are called prime pairs, such as 5 and 7, 17 and 19, etc. This problem requires finding all prime pairs where both numbers are less than or equal to n.
Input: A positive integer n (1 ≤ n ≤ 10000).
Output: All prime pairs less than or equal to n. Each pair should be output on a new line, separated by a single space. If no prime pairs are found, output “empty”.
Sample Input: 100Sample Output: 3 55 711 1317 1929 3141 4359 6171 73
Analysis: According to the problem statement, two numbers must differ by 2 and both must be prime. That is, if i is prime, then i + 2 must also be prime, so output i and i + 2. Mark as true once found. If the marked state is false, it indicates none were found.
/**/
#include<bits/stdc++.h>
using namespace std;
// Function to check if a number is prime
bool prime(int n){
if(n==1||n<=0) return false ;
else{
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
return false ;
}
}
}return true;
}
int main(){
int n;
cin>>n;
bool flag=false;
for(int i=3;i<=n-2;i++){
if(prime(i)&&prime(i+2)){
cout<<i<<" ";<<i+2<<endl;
flag=true;
}
}
if(flag==false){
cout<<"empty";
}
return 0;
}
Previous Issues:
C++ Sieve Method for Prime Checking (Sieve of Eratosthenes and Linear Sieve)
C++ Daily Practice – Informatics Olympiad Comprehensive Guide 1151: Count of Primes
C++ Daily Practice – Informatics Olympiad Comprehensive Guide 1099: The n-th Smallest Prime
C++ Daily Practice – Informatics Olympiad Comprehensive Guide 2030: [Example 4.16] Finding Primes
