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.
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.
number=4 Expected result=T-prime because factors of 4 are 1, 2 and 4 only
number=15 Expected result=NOT T-prime because 15 has more than 3 factors( 1, 3, 5 and 15)
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.
using namespace std;
long long int i,j,n;
long long int x;
long long int m=1000001;
//generate prime numbers
set<long long int> st;
//seive of eratosthenes
//put all the t_primes in the set
cout<<"How many numbers ?"<<endl;
cout<<endl<<"Enter the number "<<endl;
cout<<x<<" is T-prime";
cout<<x<<" is NOT T-prime";
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.