生成 2 到 10,000 之间的数字。打印出来的数字只能是2个素数的倍数

Question

家庭作业：我简直被难住了。我设置了算法，但我不知道如何编写代码

需要说明的是，您不需要数组或通过引用传递变量。

该项目的目的是分解问题并使用 Top-Down_Design 或草稿本方法开发算法。

问题：

检查2到10000之间的数字，如果是Dual_Prime则输出。

我将 DualPrime 称为两个素数的乘积。 Ad 其中两个素数不相等。所以9不是对偶素数。 15 是 (3 * 5)。输出每行有 10 个数字。

我的算法设置

第 1 步：查找质数。:

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

第 2 步：将质数存储在数组中

第 3 步：将每个数组相互相乘

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

第 4 步：冒泡排序

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;
            }
}

第 5 步：按 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,

虽然动态数组和 Eratosthenes 筛法更可取，但我尝试编写最低限度 固定版本的代码。

首先，我们定义了以下全局变量，这些变量在您最初的 Multiply_Prime_Numbers 实现中使用。 (Please check this post.)

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

接下来我们修复Prime_Number如下。原代码中条件number%1==0不合适：

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;
}

此外，Multiply_Prime_Numbers应该用双for循环实现如下：

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;
        }        
    }
}

那么这些函数的作用如下。 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

Sieve of Eratosthenes 是一种已知的算法，可以加快搜索所有素数的速度，达到一定数量。

OP 可以使用它来实施其实施的第一步，但他们也可以对其进行调整以避免排序步骤。

给出所有素数的列表（最多要检查的最大数的一半）：

创建一个与要检查的数字范围一样大的布尔数组。
使用两个嵌套循环将每对不同的质数相乘。
如果乘积小于10000（最大值）则将数组对应元素设置为true。否则跳出内循环。
完成后，遍历数组，如果值为真，则打印对应的索引。

这里有一个 proof of concept（在没有 OP 的分配限制的情况下实现）。

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 * 2; 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";
}

生成 2 到 10,000 之间的数字。打印出来的数字只能是2个素数的倍数

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

c++

prime-factoring