Generate numbers from 2 to 10,000. The numbers printed can only be a multiple of 2 prime numbers

Question

Homework: I'm just stumped as hell. I have algorithms set up, but I have no idea how to code this

Just to be clear you do not need arrays or to pass variables by reference.

The purpose of the project is to take a problem apart and using Top-Down_Design or scratch pad method develop the algorithm.

Problem:

Examine the numbers from 2 to 10000. Output the number if it is a Dual_Prime.

I will call a DualPrime a number that is the product of two primes. Ad where the two primes are not equal . So 9 is not a dual prime. 15 is ( 3 * 5 ) . The output has 10 numbers on each line.

My Algorithm set-up

Step 1: find prime numbers.:

bool Prime_Number(int number)
{
    for (int i = 2; i <= sqrt(number); i++)
    {
        if (number % 1 == 0)
            return false;
    }
    return true;
}

Step 2: store prime numbers in a array

Step 3: Multiply each array to each other

void Multiply_Prime_Numbers(int Array[], int Size)
{
    for (int j = 0; j < Size- 1; j++)
    {
        Dual_Prime[] =  Arr[j] * Arr[j + 1]  
    }
}

Step 4: Bubble sort

void Bubble_Sort(int Array[], int Size) // Sends largest number to the right
{
    for (int i = Size - 1; i > 0; i--)
        for (int j = 0; j < i; j++)
            if (Array[j] > Array[j + 1])
            {
                int Temp = Array[j + 1];
                Array[j + 1] = Array[j];
                Array[j] = Temp;
            }
}

Step 5: Display New Array by rows of 10

void Print_Array(int Array[], int Size)
{
    for (int i = 0; i < Size; i++)
    {
        cout << Dual_Prime[i] << (((j % 10) == 9) ? '\n' : '\t');
    }
    cout << endl;
}

Answer 1

I haven't learned dynamic arrays yet,

Although dynamic arrays and the sieve of Eratosthenes are more preferable, I tried to write minimally fixed version of your code.

First, we define following global variables which are used in your original implementation of Multiply_Prime_Numbers. (Please check this post.)

constexpr int DP_Size_Max = 10000;
int DP_Size = 0;
int Dual_Prime[DP_Size_Max];

Next we fix Prime_Number as follows. The condition number%1==0 in the original code is not appropriate:

bool Prime_Number(int number)
{
    if(number<=1){
        return false;
    }

    for (int i = 2; i*i <= number; i++)
    {
        if (number % i == 0)
            return false;
    }

    return true;
}

In addition, Multiply_Prime_Numbers should be implemented by double for-loops as follows:

void Multiply_Prime_Numbers(int Array[], int Size)
{    
    for (int i = 0; i < Size; ++i)
    {
        for (int j = i+1; j < Size; ++j)
        {
            Dual_Prime[DP_Size] = Array[i]*Array[j];

            if(Dual_Prime[DP_Size] >= DP_Size_Max){
                return;
            }

            ++DP_Size;
        }        
    }
}

Then these functions work as follows. Here's a DEMO of this minimally fixed version.

int main()
{
    int prime_numbers[DP_Size_Max];
    int size = 0;

    for(int j=2; j<DP_Size_Max; ++j)
    {
        if(Prime_Number(j)){
            prime_numbers[size]=j;
            ++size;
        }
    }

    Multiply_Prime_Numbers(prime_numbers, size);
    Bubble_Sort(Dual_Prime, DP_Size);

    for(int i=0; i<DP_Size;++i){
        std::cout << Dual_Prime[i] << (((i % 10) == 9) ? '\n' : '\t');;
    }
    std::cout << std::endl;

    return 0;
}

Answer 2

The Sieve of Eratosthenes is a known algorithm which speeds up the search of all the primes up to a certain number.

The OP can use it to implement the first steps of their implementation, but they can also adapt it to avoid the sorting step.

Given the list of all primes (up to half the maximum number to examine):

• Create an array of bool as big as the range of numbers to be examined.

• Multiply each distinct couple of primes, using two nested loops.

• If the product is less than 10000 (the maximum) set the corrisponding element of the array to true. Otherwise break out the inner loop.

• Once finished, traverse the array and if the value is true, print the corresponding index.

Here there's a proof of concept (implemented without the OP's assignment restrictions).

Answer 3

// Ex10_TwoPrimes.cpp : This file contains the 'main' function. Program execution begins and ends there.


#include "pch.h"
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

void Homework_Header(string Title);
void Do_Exercise();
void Sieve_Of_Eratosthenes(int n);
void Generate_Semi_Prime();

bool Semi_Prime(int candidate);
bool prime[5000 + 1];

int main()
{
    Do_Exercise();

    cin.get();
    return 0;
}

void Do_Exercise()
{
    int n = 5000;

    Sieve_Of_Eratosthenes(n);

    cout << endl;

    Generate_Semi_Prime();
}

void Sieve_Of_Eratosthenes(int n)
{
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 

    memset(prime, true, sizeof(prime));

    for (int p = 2; p*p <= n; p++)
    {
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true)
        {
            // Update all multiples of p 
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}

bool Semi_Prime(int candidate)
{
    for (int index = 2; index <= candidate / 2; index++)
    {
        if (prime[index])
        {
            if (candidate % index == 0)
            {
                int q = candidate / index;
                if (prime[q] && q != index)
                    return true;
            }
        }
    }
    return false;
}

void Generate_Semi_Prime()
{
    for (int i = 2; i <= 10000; i++)
        if (Semi_Prime(i)) cout << i << "\t";
}