Генерация чисел от 2 до 10000. Напечатанные числа могут быть кратны двум простым числам - PullRequest
Новая
       12

Генерация чисел от 2 до 10000. Напечатанные числа могут быть кратны двум простым числам

0 голосов
/ 07 ноября 2018

Домашнее задание: я просто ошеломлен У меня настроены алгоритмы, но я не знаю, как это кодировать

Просто чтобы прояснить ситуацию, вам не нужны массивы или переменные для передачи по ссылке.

Цель проекта - разобрать проблему и разработать алгоритм с помощью метода Top-Down_Design или блокнота.

Проблема:

Проверьте числа от 2 до 10000. Выведите число, если это Dual_Prime.

Я назову DualPrime числом, которое является произведением двух простых чисел. Объявление, где два простых числа не равны. Итак, 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;
}

Ответы [ 3 ]

0 голосов
/ 08 ноября 2018

Сито Эратосфена - это известный алгоритм, который ускоряет поиск всех простых чисел до определенного числа.

ОП может использовать его для реализации первых шагов их реализации, но они также могут адаптировать его, чтобы избежать этапа сортировки.

С учетом списка всех простых чисел (до половины максимального числа для изучения):

  • Создайте массив bool размером с исследуемый диапазон чисел.

  • Умножьте каждую отдельную пару простых чисел, используя два вложенных цикла.

  • Если произведение меньше 10000 (максимум), установите соответствующий элемент массива в значение true. В противном случае разорвать внутренний цикл.

  • После завершения просмотрите массив и, если значение равно true, выведите соответствующий индекс.

Здесь есть подтверждение концепции (реализовано без ограничений присвоения ОП).

0 голосов
/ 12 ноября 2018 
// 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";
}
0 голосов
/ 07 ноября 2018

Я еще не выучил динамические массивы,

Хотя динамические массивы и сито Эратосфена более предпочтительны, я попытался написать минимально исправленную версию вашего кода.

Сначала мы определим следующие глобальные переменные, которые используются в вашей первоначальной реализации Multiply_Prime_Numbers. ( Пожалуйста, проверьте этот пост. ) 

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

Тогда эти функции работают следующим образом. Вот ДЕМО этой минимально исправленной версии. 

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