Заполняя массив целым числом, затем используя пробное деление, найдите простые числа меньше N
Предполагается, что эта функция принимает три параметра и находит простые числа меньше, чем NUM, введенное с использованием пробного деления.
void trialDivision(int prime[], const int NUM, const int SIZE) {
int j = NUM;
for (int i = 0; i < NUM; i++) {
prime[i] = 1;
}
for (int i = 2; i <= sqrt(NUM); i++, j++) {
put numbers less than n into array
}
Затем выполните пробное деление, чтобы найти простые числа.
У меня проблема с выяснением, как поместить в функцию числа, меньшие, чем sqrt (NUM).
Спасибо
Решение
Во-первых, вы хотите создать цикл, который идет от i=2 в i<NUM, Это проверяет каждое положительное целое число больше 1 до NUM-1 на предмет простоты. Это будет выглядеть примерно так:
for (int i=2;i<NUM;i++)
{
// prime checking
}
Теперь для фактической первичной проверки. Давайте поместим это в функцию. Здесь вы бы использовали sqrt() определить верхнюю границу цикла. Еще раз мы начинаем наш цикл в j=2 потому что все числа делятся на 1, поэтому нет необходимости включать это.
bool isPrime(int i)
{
for (int j=2;j<sqrt(i);j++)
{
if (i%j==0)
{
return false;
}
}
return true;
}
В принципе, если цикл завершается, то мы не нашли никаких факторов i между 2 а также sqrt(i)так что это просто.
Теперь просто вызовите эту функцию в вашем первом цикле.
for (int i=2;i<NUM;i++)
{
if (isPrime(i))
{
prime[i] = 1; // or whatever you want to use to represent a prime. If you use 1, it's best if you initiate the array with 0's
}
}
Если вы хотели просто список простых чисел, то std::vector<int> будет лучшим выбором для хранения ваших результатов.
Другие решения
Других решений пока нет …