# T-Primes Problem using Dynamic Programming

«
»

This is a C++ Program that Solves T Primes Problem using Dynamic Programming technique.

Problem Description

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

Problem Solution

The key to solve this problem is an observation that the t-primes are the numbers which squares of a prime number.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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.

Expected Input and Output

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.```
Program/Source Code

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.

1. ` `
2. `//tprimes`
3. `#include<bits/stdc++.h>`
4. `using namespace std;`
5. ` `
6. `int main()`
7. `{`
8. `    long long int i,j,n;`
9. `    long long int x;`
10. `    long long int m=1000001;`
11. ` `
12. `    //generate prime numbers `
13. `    vector<bool> primes(1000001,true);`
14. `    set<long long int> st;`
15. `    primes[0]=primes[1]=false;`
16. ` `
17. `    //seive of eratosthenes`
18. `    for(i=2;i*i<=m;i++)`
19. `    {`
20. `        if(primes[i])`
21. `        {`
22. `            for(j=i;i*j<=m;j++)`
23. `            {`
24. `                primes[i*j]=false;`
25. `            }`
26. `        }`
27. `    }`
28. ` `
29. `    //put all the t_primes in the set`
30. `    for(i=2;i<=m;i++)`
31. `    {`
32. `        if(primes[i])`
33. `            st.insert(i*i);`
34. `    }`
35. ` `
36. `    cout<<"How many numbers ?"<<endl;`
37. `    cin>>n;`
38. ` `
39. `    while(n--)`
40. `    {`
41. `        cout<<endl<<"Enter the number "<<endl;`
42. `        cin>>x;`
43. ` `
44. `        if(st.find(x)!=st.end())`
45. `            cout<<x<<" is T-prime";`
46. ` `
47. `        else`
48. `            cout<<x<<" is NOT T-prime";`
49. ` `
50. `        cout<<endl;`
51. `    }`
52. ` `
53. `    return 0;`
54. `}`
Program Explanation

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.

Runtime Test Cases
```
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.