Step by Step solution about How to resolve the algorithm Long primes step by step in the C++ programming language

This C++ program finds and counts "long primes" up to a given limit. A "long prime" is a prime number where the period of its reciprocal is equal to the prime number minus one.

Here's a detailed breakdown of the code:

#include <iomanip>
#include <iostream>
#include <list>
using namespace std;

• These lines include the necessary C++ standard library headers for input/output operations and list container.

void sieve(int limit, list<int> &primes)
{
 bool *c = new bool[limit + 1];
 for (int i = 0; i <= limit; i++)
   c[i] = false;
 // No need to process even numbers
 int p = 3, n = 0;
 int p2 = p * p;
 while (p2 <= limit)
 {
   for (int i = p2; i <= limit; i += 2 * p)
     c[i] = true;
   do
     p += 2;
   while (c[p]);
   p2 = p * p;
 }
 for (int i = 3; i <= limit; i += 2) 
   if (!c[i]) 
     primes.push_back(i);
 delete [] c;
}

• This sieve function implements the Sieve of Eratosthenes algorithm to efficiently find prime numbers up to a specified limit.
  • It creates a boolean array c of size limit + 1 and initializes all elements to false.
  • It starts with the prime number p = 3 and iteratively marks multiples of p as non-prime (true) in the c array.
  • It updates p to the next unmarked (false) value until it reaches the square root of the limit.
  • Finally, it iterates through the c array to populate the primes list with the prime numbers.

int findPeriod(int n) 
{
 int r = 1, rr, period = 0;
 for (int i = 1; i <= n + 1; ++i)
   r = (10 * r) % n;
 rr = r;
 do
 {
   r = (10 * r) % n;
   period++;
 }
 while (r != rr);
 return period;
}

• The findPeriod function finds the period of the reciprocal of an integer n.
  • It initializes r to 1 and iterates until r becomes 0, counting the number of iterations (period).
  • The period of the reciprocal of n is the number of iterations it takes for r to repeat.

int main()
{
 int count = 0, index = 0;
 int numbers[] = {500, 1000, 2000, 4000, 8000, 16000, 32000, 64000};
 list<int> primes;
 list<int> longPrimes;
 int numberCount = sizeof(numbers) / sizeof(int);
 int *totals = new int[numberCount];

• The main function is the program's entry point.
  • It initializes variables and data structures.
  • numbers is an array of integers up to which we want to find long primes.
  • primes will store the prime numbers up to 64000, and longPrimes will store the long primes.
  • count stores the total number of long primes found, and index tracks the current index in the numbers array.
  • numberCount is the number of elements in the numbers array.
  • totals is an array that will store the count of long primes up to each value in numbers.

 cout << "Please wait." << endl << endl;
 sieve(64000, primes);  

• It prints a "Please wait" message to indicate that the program is working.
• The sieve function is called to find all prime numbers up to 64000 and store them in the primes list.

 for (list<int>::iterator iterPrime = primes.begin();  
   iterPrime != primes.end(); 
   iterPrime++)
 {  
   if (findPeriod(*iterPrime) == *iterPrime - 1)
     longPrimes.push_back(*iterPrime);
 } 

• It iterates through the primes list using an iterator iterPrime.
• For each prime number, it calls the findPeriod function to find the period of its reciprocal.
• If the period is equal to the prime number minus one, it means it's a long prime, and it's added to the longPrimes list.

 for (list<int>::iterator iterLongPrime = longPrimes.begin();
   iterLongPrime != longPrimes.end(); 
   iterLongPrime++)
 {
   if (*iterLongPrime > numbers[index])
     totals[index++] = count;
       ++count;
 }

• It iterates through the longPrimes list using an iterator iterLongPrime and counts the number of long primes found up to each value in the numbers array.
• count keeps track of the total number of long primes, and index tracks the current index in the numbers array.

 totals[numberCount - 1] = count;

• After processing all long primes, it sets the last element of the totals array to the total count of long primes.

 cout << "The long primes up to " << totals[0] << " are:" << endl;
 cout << "[";
 int i = 0;
 for (list<int>::iterator iterLongPrime = longPrimes.begin(); 
   iterLongPrime != longPrimes.end() && i < totals[0]; 
   iterLongPrime++, i++)
 {  
   cout << *iterLongPrime << " ";
 }  
 cout << "\b]" << endl;

• It prints the list of long primes up to the first value in the numbers array.

 cout << endl << "The number of long primes up to:" << endl;
 for (int i = 0; i < 8; ++i)
   cout << "  " << setw(5) << numbers[i] << " is " << totals[i] << endl;

• Finally, it prints the count of long primes up to each value in the numbers array.

#include <iomanip>
#include <iostream>
#include <list>
using namespace std;
  
void sieve(int limit, list<int> &primes)
{
  bool *c = new bool[limit + 1];
  for (int i = 0; i <= limit; i++)
    c[i] = false;
  // No need to process even numbers
  int p = 3, n = 0;
  int p2 = p * p;
  while (p2 <= limit)
  {
    for (int i = p2; i <= limit; i += 2 * p)
      c[i] = true;
    do
      p += 2;
    while (c[p]);
    p2 = p * p;
  }
  for (int i = 3; i <= limit; i += 2) 
    if (!c[i]) 
      primes.push_back(i);
  delete [] c;
}
 
// Finds the period of the reciprocal of n
int findPeriod(int n) 
{
  int r = 1, rr, period = 0;
  for (int i = 1; i <= n + 1; ++i)
    r = (10 * r) % n;
  rr = r;
  do
  {
    r = (10 * r) % n;
    period++;
  }
  while (r != rr);
  return period;
}
 
int main()
{
  int count = 0, index = 0;
  int numbers[] = {500, 1000, 2000, 4000, 8000, 16000, 32000, 64000};
  list<int> primes;
  list<int> longPrimes;
  int numberCount = sizeof(numbers) / sizeof(int);
  int *totals = new int[numberCount];
  cout << "Please wait." << endl << endl;
  sieve(64000, primes);  
  for (list<int>::iterator iterPrime = primes.begin();  
    iterPrime != primes.end(); 
    iterPrime++)
  {  
    if (findPeriod(*iterPrime) == *iterPrime - 1)
      longPrimes.push_back(*iterPrime);
  }    
  
  for (list<int>::iterator iterLongPrime = longPrimes.begin();
    iterLongPrime != longPrimes.end(); 
    iterLongPrime++)
  {
    if (*iterLongPrime > numbers[index])
      totals[index++] = count;
        ++count;
  }
  totals[numberCount - 1] = count;
  cout << "The long primes up to " << totals[0] << " are:" << endl;
  cout << "[";
  int i = 0;
  for (list<int>::iterator iterLongPrime = longPrimes.begin(); 
    iterLongPrime != longPrimes.end() && i < totals[0]; 
    iterLongPrime++, i++)
  {  
    cout << *iterLongPrime << " ";
  }  
  cout << "\b]" << endl;
  cout << endl << "The number of long primes up to:" << endl;
  for (int i = 0; i < 8; ++i)
    cout << "  " << setw(5) << numbers[i] << " is " << totals[i] << endl;
  delete [] totals;
}