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__.