Void main()

{ ulong M,N,v,k,m;

printf("N = "); scanf("%lu",&N);

M = (N<=200 ? 1.6*N/log(N)+1 : N/(log(N)-2)+1);

printf("M = %lu \n", M);

ulong* x = new ulong[M];

x[0]=1; x[1]=2; x[2]=3; m=3; v=5;

while (v<=N) { for (k=2;k<m;k++) if (v%x[k]==0) break;

if (k==m) x[m++]=v;

v+=2;

}

printf("m = %lu \n", m);

for (k=0;k<m;k++) printf("%6lu",x[k]); puts("");

delete[] x;

}

Генерація підмножин

Задача

Задано пару додатних цілих чисел n,r, причому r £ n. Потрібно вивести на екран всі r-елементні підмножини із множини чисел, що належать відрізку [0, n-1].

Алгоритм

Для збереження елементів поточної підмножини будемо застосовувати r-елементний масив A[0], A[1], ... , A[r-1]. Елементи поточної підмножини будемо подавати у монотонно зростаючому порядку. Не дуже важко зрозуміти, що у такому разі елемент робочого масиву A[k] не може отримати значення більше, ніж n-r+k . Алгоритм побудуємо наступним чином.

1. Нехай k = r-1.

2. Збільшуємо A[k] на одиницю.

Якщо A[k] £ n-r+k , виконуємо присвоєння A[i+1]=A[i]+1 для всіх i від k+1 до r-2 , тобто до кінця масиву А. Масив А буде вміщувати чергову шукану підмножину. Вивести її на екран. Перейти до п.1.

Якщо ні, то зменшити k на одиницю.

Якщо k<0 , то завершити процес.

Якщо ні, то перейти до п.2.

Програмна реалізація наведеного алгоритму для довільних n,r наведена нижче. Для збереження поточної підмножини A застосовується динамічний масив.

// Приклад 1

#include <syst.h>