This is a C++ Program that Solves T Primes Problem using Dynamic Programming technique.
We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we’ll call a positive integer t Т-prime, if t has exactly three distinct positive divisors.
You are given an array of n positive integers. For each of them determine whether it is Т-prime or not.
Constraints
Number to check for T-prime, x (1 <= x <= 10^12).
The key to solve this problem is an observation that the t-primes are the numbers which squares of a prime number.
First we will implement sieve of eratosthenes to identify all prime numbers upto 10^6 (because 10^6 is the square root of highest value of number allower which is 10^12). Then, for all the prime number identified we will store their squares in a set. These numbers are T-primes. Finally, we will simply check whether the number to test is in the set or not.
Case-1:
number=4 Expected result=T-prime because factors of 4 are 1, 2 and 4 only
Case-2:
number=15 Expected result=NOT T-prime because 15 has more than 3 factors( 1, 3, 5 and 15)
Case-3:
number=49 Expected result=T-prime because 49 has exactly 3 factors 1, 7, 49.
Here is source code of the C++ Program to Solve T-Primes problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
//tprimes
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int i,j,n;
long long int x;
long long int m=1000001;
//generate prime numbers
vector<bool> primes(1000001,true);
set<long long int> st;
primes[0]=primes[1]=false;
//seive of eratosthenes
for(i=2;i*i<=m;i++)
{
if(primes[i])
{
for(j=i;i*j<=m;j++)
{
primes[i*j]=false;
}
}
}
//put all the t_primes in the set
for(i=2;i<=m;i++)
{
if(primes[i])
st.insert(i*i);
}
cout<<"How many numbers ?"<<endl;
cin>>n;
while(n--)
{
cout<<endl<<"Enter the number "<<endl;
cin>>x;
if(st.find(x)!=st.end())
cout<<x<<" is T-prime";
else
cout<<x<<" is NOT T-prime";
cout<<endl;
}
return 0;
}
In the main function, we first implement sieve of eratosthenes for identifying prime numbers. Then, we stored the square of all the prime numbers in a set. At this point, we will take input for number of test cases and the numbers to test. For each number, we will display its verdict.
Case-1: $ g++ t_prime.cpp $ ./a.out How many numbers ? 3 Enter the number 4 4 is T-prime Enter the number 5 5 is NOT T-prime Enter the number 6 6 is NOT T-prime Case-2: $ ./a.out How many numbers ? 3 Enter the number 10 10 is NOT T-prime Enter the number 15 15 is NOT T-prime Enter the number 49 49 is T-prime Case-3: $ ./a.out How many numbers ? 4 Enter the number 12 12 is NOT T-prime Enter the number 55 55 is NOT T-prime Enter the number 121 121 is T-prime Enter the number 145 145 is NOT T-prime
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Check Data Structure Books
- Apply for Computer Science Internship
- Check Programming Books
- Check Computer Science Books
- Practice Design & Analysis of Algorithms MCQ