Информатика и технология программирования

Простые числа


Сформировать массив простых чисел, не превышающих заданное. Простое число -число, которое делится нацело только на 1 и на само себя.

Шаг 1: Исходные данные и результат -формальные параметры функции -аналогично предыдущему примеру.


void calc(int val, int A[], int n) {...}

Шаг 2: Сущность алгоритма состоит в проверке всех чисел от 2 до val и сохранении их в массиве, если они простые.


void calc(int val, int A[], int n)
{
int i; // Номер очередного простого часла


int m; // Очередное проверяемое число


for (i=0, m=2; i &#60 n-1 &#38&#38 m &#60 val; m++)
{
if (m - простое число)
A[i++] = m;
}
A[i] = 0;
}

Шаг 3: Конкретизируем утверждение, что m -простое число. Во-первых, оно не делится ни на одно число в диапазоне от 2 до m/2 включительно. Во-вторых, что то же самое, оно не делится ни на одно простое число от 2 до m-1. Тогда можно воспользоваться накопленными простыми числами в массиве A от A[0] до А[i-1]. Фрагмент программы, где определяется "простота" числа будет иметь вид:


int n;
for (n=0; n &#60 i; n++)
if (m % A[n]==0) break; // Разделилось нацело


if (i==n)
{ ...m - простое число... }

Окончательный вариант:


//------------------------------------------------------bk32-02.cpp


//-------Простые числа


void calc(int val, int A[], int n)
{
int i,m,k;
for (i=0, m=2; i &#60 n-1 &#38&#38 m &#60 val; m++)
{
for (k=0; k &#60 i; k++)
if (m % A[k]==0) break;
if (i==k)
A[i++] = m;
}
A[i] = 0;
}



Содержание раздела