(C ++) Поиск всех простых чисел между двумя целыми числами (без использования решета Эратосфана) - PullRequest
Новая
       43

(C ++) Поиск всех простых чисел между двумя целыми числами (без использования решета Эратосфана)

0 голосов
/ 23 октября 2018

Я пытаюсь найти все простые числа между двумя целыми числами и поместить их в массив целых чисел.

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

Мой код успешно запрашивает у пользователя два целых числа, но пока я не использую ни одно из них.Во-первых, я хочу убедиться, что программа работает для значений от 0 до любого значения, в данном случае 200 только для ее проверки.

Проблема в том, что когда я запускаю программу и печатаю первые 20 или около того значений в массивеЯ получаю

2, 3, 5, 7, 11, 200, 0, 0, 0, 0, 0, 0 ...... больше нулей.

Theпервые 5 значений верны, потому что они начинаются в массиве, но после этого все становится бесполезным.

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

Вот мой код: 

#include "stdafx.h"
#include "iostream"
#include "climits"
#include "cmath"
#include "array"
using namespace std;


int main()
{

// declare variables to store user input
int lowerBound, upperBound;

// prompt user for lesser and greater integers and store them
cout << "Program to find all primes between two integers." << endl;
cout << "Enter lesser integer: " << endl;
cin >> lowerBound;
cout << "Enter greater integer: " << endl;
cin >> upperBound;

// if statement to switch the input variables if the user accidentally enters them backwards
if (lowerBound > upperBound) {
    int temp = lowerBound;
    lowerBound = upperBound;
    upperBound = temp;
}

// initialize int array with the first 5 primes
int primes[100] = { 2, 3, 5, 7, 11 };

// loop to find primes between 12 and 200 (since we already have primes from 1-11 in the array)
for (int i = 12; i <= 200; i++) {

    // the maximum divisor needed to determine if the current integer being tested is prime
    double maxDivisor = sqrt(i);

    // variable for the current size of the array
    int size = 5;

    // boolean variable is set to true by default
    bool isPrime = true;

    for (int j = 0; j < size; j++) {     // changed "j<=size" to "j<size"
        int remainder = (i % primes[j]);

        // once the maximum divisor is reached, there is no need to continue testing for the current integer
        if (primes[j] > maxDivisor) {
            break;
        }

        // if the remainder of divison by a prime is 0, the number is not prime, so set the boolean variable to false
        if (remainder = 0) {
            isPrime = false;
        }
    }

    // if isPrime is still true after the nested loop, the integer value being tested will be placed in the next element of the array
    if (isPrime == true) {
        primes[size] = i;

        // since we added to the array, increment size by 1
        size++;
    }

}

// display the first 20 values in the array for debugging
for (int k = 0; k < 20; k++) {
    cout << primes[k] << ", ";
}

system("pause");
return 0;
}

1 Ответ

0 голосов
/ 23 октября 2018

Это здесь 

if (remainder = 0) {
    isPrime = false;
}

Необходимо изменить на 

if (remainder == 0) {
    isPrime = false;
}

Поскольку = выполняет присваивание, а не сравнение.Так что remainder = 0 делает для него remainder равным 0, а затем возвращает 0, который приводится к false, что является одной из причин, по которой он не находит простых чисел.

Кроме того, как отметил Фантастический мистер Фокс, for (int j = 0; j <= size; j++) необходимо изменить на for (int j = 0; j < size; j++).

Кроме того, ваш компилятор выдавал какие-либо предупреждения?Если нет, попробуйте посмотреть, можете ли вы установить более строгие предупреждения.Я полагаю, что большинство современных компиляторов подскажут вам if (remainder = 0).Получение полезных предупреждений от компилятора очень помогает в предотвращении ошибок.

Редактировать: Как отметил Карстен Куп, вы должны переместить int size = 5; из цикла до for (int i = 12;.С этими изменениями он теперь работает на моей машине.

И последнее, но не менее важное: совет: вместо if (isPrime == true) вы можете просто написать if (isPrime).

...