How to resolve the algorithm Prime conspiracy step by step in the C++ programming language
How to resolve the algorithm Prime conspiracy step by step in the C++ programming language
Table of Contents
Problem Statement
A recent discovery, quoted from Quantamagazine (March 13, 2016): and
The task is to check this assertion, modulo 10. Lets call i -> j a transition if i is the last decimal digit of a prime, and j the last decimal digit of the following prime.
Considering the first one million primes. Count, for any pair of successive primes, the number of transitions i -> j and print them along with their relative frequency, sorted by i . You can see that, for a given i , frequencies are not evenly distributed.
(Modulo 10), primes whose last digit is 9 "prefer" the digit 1 to the digit 9, as its following prime.
Do the same for one hundred million primes.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Prime conspiracy step by step in the C++ programming language
1. Overview
This code, written in C++, explores the transition probabilities of final digits of consecutive prime numbers. It generates 1 million prime numbers and calculates the frequency of transitions from one final digit (last digit) to the next.
2. Generating Prime Numbers
The code uses two different methods to generate prime numbers:
- isPrime() Function: A simple function that implements the sieve of Eratosthenes to check if a given number is prime.
- primesieve Library: An external library (not shown in the code) that efficiently generates prime numbers.
3. Calculating Transitions
Once the list of primes is generated, the code calculates the transition probabilities using the following logic:
- It iterates over the list of primes.
- For each consecutive prime pair
(p, p+1), it extracts their last digits(d1, d2)as a pair(d1, d2). - It stores the frequency of the transition
(d1, d2)in a mapconspiracyusingstd::pair<int, int>as the key.
4. Custom Comparator Class
To sort the transitions in the conspiracy map, the code defines a custom comparator class Compare that compares pairs (a, b) as follows:
- If
a.first(first digit) is different fromb.first, it returnsa.first < b.first. - If
a.firstis the same, it returnsa.second < b.second.
5. Printing Results
The code then prints the transition frequencies, sorted by the first digit of the transition. For each transition (d1, d2), it prints the following information:
d1 -> d2: The transition from the first digit to the second digit.count: The frequency of the transition.frequency: The percentage of transitions from the first digit to the second digit, calculated as(count / total_transitions) * 100.
6. Using primesieve Library (Optional)
In the optional section of the code, it uses the primesieve library for more efficient prime number generation. It computes transitions for 1 million and 100 million prime numbers.
7. Caveats
- The code only considers prime numbers whose last digits are in the range
[0, 9]. - It does not check for overflow when computing transition probabilities.
Source code in the cpp programming language
#include <vector>
#include <iostream>
#include <cmath>
#include <utility>
#include <map>
#include <iomanip>
bool isPrime( int i ) {
int stop = std::sqrt( static_cast<double>( i ) ) ;
for ( int d = 2 ; d <= stop ; d++ )
if ( i % d == 0 )
return false ;
return true ;
}
class Compare {
public :
Compare( ) {
}
bool operator( ) ( const std::pair<int , int> & a , const std::pair<int, int> & b ) {
if ( a.first != b.first )
return a.first < b.first ;
else
return a.second < b.second ;
}
};
int main( ) {
std::vector<int> primes {2} ;
int current = 3 ;
while ( primes.size( ) < 1000000 ) {
if ( isPrime( current ) )
primes.push_back( current ) ;
current += 2 ;
}
Compare myComp ;
std::map<std::pair<int, int>, int , Compare> conspiracy (myComp) ;
for ( int i = 0 ; i < primes.size( ) -1 ; i++ ) {
int a = primes[i] % 10 ;
int b = primes[ i + 1 ] % 10 ;
std::pair<int , int> numbers { a , b} ;
conspiracy[numbers]++ ;
}
std::cout << "1000000 first primes. Transitions prime % 10 → next-prime % 10.\n" ;
for ( auto it = conspiracy.begin( ) ; it != conspiracy.end( ) ; it++ ) {
std::cout << (it->first).first << " -> " << (it->first).second << " count:" ;
int frequency = it->second ;
std::cout << std::right << std::setw( 15 ) << frequency << " frequency: " ;
std::cout.setf(std::ios::fixed, std::ios::floatfield ) ;
std::cout.precision( 2 ) ;
std::cout << (static_cast<double>(frequency) / 1000000.0) * 100 << " %\n" ;
}
return 0 ;
}
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <primesieve.hpp>
void compute_transitions(uint64_t limit) {
primesieve::iterator it;
std::map<std::pair<uint64_t, uint64_t>, uint64_t> transitions;
for (uint64_t count = 0, prev = 0; count < limit; ++count) {
uint64_t prime = it.next_prime();
uint64_t digit = prime % 10;
if (prev != 0)
++transitions[std::make_pair(prev, digit)];
prev = digit;
}
std::cout << "First " << limit << " prime numbers:\n";
for (auto&& pair : transitions) {
double freq = (100.0 * pair.second)/limit;
std::cout << pair.first.first << " -> " << pair.first.second
<< ": count = " << std::setw(7) << pair.second
<< ", frequency = " << std::setprecision(2)
<< std::fixed << freq << " %\n";
}
}
int main(int argc, const char * argv[]) {
compute_transitions(1000000);
compute_transitions(100000000);
return 0;
}
You may also check:How to resolve the algorithm Greatest element of a list step by step in the Excel programming language
You may also check:How to resolve the algorithm Summarize primes step by step in the Ruby programming language
You may also check:How to resolve the algorithm Averages/Mean angle step by step in the Go programming language
You may also check:How to resolve the algorithm Number names step by step in the Euphoria programming language
You may also check:How to resolve the algorithm Generate lower case ASCII alphabet step by step in the Swift programming language