How to resolve the algorithm Prime numbers whose neighboring pairs are tetraprimes step by step in the C++ programming language

Published on 7 June 2024 03:52 AM
#cpp

How to resolve the algorithm Prime numbers whose neighboring pairs are tetraprimes step by step in the C++ programming language

Table of Contents

Problem Statement

The following definitions are needed for this task. A tetraprime is a positive integer which is the product of four distinct primes. For example, 1155 is a tetraprime because 1155 = 3 x 5 x 7 x 11. The neighboring pairs of a prime are the two consecutive numbers immediately preceding or immediately following that prime. For example, (5, 6) and (8, 9) are the neighboring pairs of the prime 7.

  1. Find and show here all primes less than 100,000 whose preceding neighboring pair are both tetraprimes.
  2. Find and show here all primes less than 100,000 whose following neighboring pair are both tetraprimes.
  3. Of the primes in 1 and 2 above how many have a neighboring pair one of whose members has a prime factor of 7?
  4. For the primes in 1 and 2 above, consider the gaps between consecutive primes. What are the minimum, median and maximum gaps?
  5. Repeat these calculations for all primes less than 1 million but for 1 and 2 just show the number of primes - don't print them out individually. If it is difficult for your language to meet all of these requirements, then just do what you reasonably can.

Repeat the calculations for all primes less than 10 million.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Prime numbers whose neighboring pairs are tetraprimes step by step in the C++ programming language

The C++ program finds tetraprimes under a certain limit and analyzes their gaps and occurrences relative to primes that have tetraprime neighbors.

Notes on the Code:

  • The program uses the Sieve of Eratosthenes to generate primes less than 10 million.

  • largest_less_than: Finds the largest prime less than a given limit.

  • median: Calculates the median of a list of numbers.

  • is_tetraPrime: Checks if a number is a tetraprime (a prime with four prime factors, counting multiplicities).

  • In the main function:

    • It calculates the largest prime less than 100,000, 1,000,000, and the maximum prime.
    • It initializes vectors to store tetraprimes and their gaps.
    • It initializes counters for tetraprimes with a 7 factor in their neighbors.
    • The program iterates through the generated primes.
    • For each prime, it checks if the previous and next two numbers are also tetraprimes.
    • It counts the occurrences and 7 factor cases for both preceding and following tetraprimes.
    • At certain limits (100,000, 1,000,000, and the maximum prime), it prints the tetraprimes found and their statistics.
    • The program analyzes the gaps between these tetraprimes, calculating minimum, median, and maximum.

Source code in the cpp programming language

#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

std::vector<uint32_t> primes;

void sieve_primes(const uint32_t& limit) {
	std::vector<bool> marked_prime(limit + 1, true);

	for ( uint32_t i = 2; i * i <= limit; ++i ) {
		if ( marked_prime[i] ) {
			for ( uint32_t j = i * i; j <= limit; j += i ) {
				marked_prime[j] = false;
			}
		}
	}

	for ( uint32_t i = 2; i <= limit; ++i ) {
		if ( marked_prime[i] ) {
			primes.emplace_back(i);
		}
	}
}

uint32_t largest_less_than(const uint32_t& n) {
    auto lower = std::lower_bound(primes.begin(), primes.end(), n);
    return primes[std::distance(primes.begin(), lower) - 1];
}

uint32_t median(const std::vector<uint32_t>& list) {
	if ( list.size() % 2 == 0 ) {
		return ( list[list.size() / 2 - 1] + list[list.size() / 2] ) / 2;
	}
	return list[list.size() / 2];
}

bool is_tetraPrime(uint32_t n) {
    uint32_t count = 0;
    uint32_t previous_factor = 1;
    for ( uint32_t prime : primes ) {
        uint64_t limit = prime * prime;
        if ( count == 0 ) {
            limit *= limit;
        } else if ( count == 1 ) {
            limit *= prime;
        }
        if ( limit <= n ) {
            while ( n % prime == 0 ) {
                if ( count == 4 || prime == previous_factor ) {
                	return false;
                }
                count++;
                n /= prime;
                previous_factor = prime;
            }
        } else {
            break;
        }
    }

    if ( n > 1 ) {
        if ( count == 4 || n == previous_factor ) {
        	return false;
        }
        count++;
    }
    return count == 4;
}

int main() {
	sieve_primes(10'000'000);

	const uint32_t largest_prime_5 = largest_less_than(100'000);
	const uint32_t largest_prime_6 = largest_less_than(1'000'000);
	const uint32_t largest_prime_7 = primes.back();
	std::vector<uint32_t> tetras_preceeding;
	std::vector<uint32_t> tetras_following;
	uint32_t sevens_preceeding = 0;
	uint32_t sevens_following = 0;
	uint32_t limit = 100'000;

	for ( const uint32_t& prime : primes ) {
	    if ( is_tetraPrime(prime - 1) && is_tetraPrime(prime - 2) ) {
	        tetras_preceeding.emplace_back(prime);
	        if ( ( prime - 1 ) % 7 == 0 || ( prime - 2 ) % 7 == 0 ) {
	        	sevens_preceeding++;
	        }
	    }

	    if ( is_tetraPrime(prime + 1) && is_tetraPrime(prime + 2) ) {
	        tetras_following.emplace_back(prime);
	        if ( ( prime + 1 ) % 7 == 0 || ( prime + 2 ) % 7 == 0 ) {
	        	sevens_following++;
	        }
	    }

	    if ( prime == largest_prime_5 || prime == largest_prime_6 || prime == largest_prime_7 ) {
	        for ( uint32_t i = 0; i <= 1; ++i ) {
	            std::vector<uint32_t> tetras = ( i == 0 ) ? tetras_preceeding : tetras_following;
	            const uint64_t size = tetras.size();
	            const uint32_t sevens = ( i == 0 ) ? sevens_preceeding : sevens_following;
	            const std::string text = ( i == 0 ) ? "preceding" : "following";

	            std::cout << "Found " << size << " primes under " << limit << " whose "
	            		  << text << " neighboring pair are tetraprimes";
	            if ( prime == largest_prime_5 ) {
	                std::cout << ":" << std::endl;
	                for ( uint64_t j = 0; j < size; ++j ) {
	                	std::cout << std::setw(7) << tetras[j] << ( ( j % 10 == 9 ) ? "\n" : "" );
	                }
	                std::cout << std::endl;
	            }
	            std::cout << std::endl;
	            std::cout << "of which " << sevens << " have a neighboring pair one of whose factors is 7."
	            		  << std::endl << std::endl;

	            std::vector<uint32_t> gaps(size - 1, 0);
	            for ( uint64_t k = 0; k < size - 1; ++k ) {
	            	gaps[k] = tetras[k + 1] - tetras[k];
	            }
	            std::sort(gaps.begin(), gaps.end());
	            const uint32_t minimum = gaps.front();
	            const uint32_t maximum = gaps.back();
	            const uint32_t middle = median(gaps);
	            std::cout << "Minimum gap between those " << size << " primes: " << minimum << std::endl;
	            std::cout << "Median  gap between those " << size << " primes: " << middle << std::endl;
	            std::cout << "Maximum gap between those " << size << " primes: " << maximum << std::endl;
	            std::cout << std::endl;
	        }
	        limit *= 10;
	    }
	}
}

You may also check:How to resolve the algorithm Look-and-say sequence step by step in the OCaml programming language
You may also check:How to resolve the algorithm Animation step by step in the Suneido programming language
You may also check:How to resolve the algorithm Literals/String step by step in the Befunge programming language
You may also check:How to resolve the algorithm Loop over multiple arrays simultaneously step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Loops/While step by step in the Dc programming language