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.

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:

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

 
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.

```
 
```
```
//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;
```
```
}
```

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.

If you find any mistake above, kindly email to [email protected]

« Prev - Boredom Problem – Dynamic Programming Solutions

» Next - Cut Ribbon Problem – Dynamic Programming Solutions

Related Posts:

Practice Computer Science MCQs
Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Practice Programming MCQs
Check Data Structure Books

Recommended Articles: