оптимизировать вложенные циклы

for( a=1; a <= 25; a++){
num1 = m[a];
for( b=1; b <= 25; b++){
num2 = m[b];
for( c=1; c <= 25; c++){
num3 = m[c];
for( d=1; d <= 25; d++){
num4 = m[d];
for( e=1; e <= 25; e++){
num5 = m[e];
for( f=1; f <= 25; f++){
num6 = m[f];
for( g=1; g <= 25; g++){
num7 = m[g];
for( h=1; h <= 25; h++){
num8 = m[h];
for( i=1; i <= 25; i++){
num = num1*100000000 + num2*10000000 +
num3*  1000000 + num4*  100000 +
num5*    10000 + num6*    1000 +
num7*      100 + num8*      10 + m[i];
check_prime = 1;

for ( y=2; y <= num/2; y++)
{
if ( num % y == 0 )
check_prime = 0;
}

if ( check_prime != 0 )
{
array[x++] = num;
}
num = 0;
}}}}}}}}}

Вы проверяете 25⁹ = 3,814,697,265,625 числа, являются ли они простыми. Это много простых тестов и всегда займет много времени. Даже в лучшем случае (для производительности), когда все записи массива (в m) равны 0 (не говоря уже о том, что тест рассматривает 0 как простое число), так что цикл пробного деления никогда не запускается, его запуск займет несколько часов. Когда все записи m положительны, код как есть будет работать в течение сотен или тысяч лет, с тех пор каждое число будет разделено пробным путем более чем на 50 000 000 чисел.

Глядя на первичную проверку,

check_prime = 1;

for ( y = 2; y <= num/2; y++)
{
if ( num % y == 0 )
check_prime = 0;
}

первая вопиющая неэффективность заключается в том, что цикл продолжается даже после того, как был найден делитель и сложность num установлено. Выйдите из цикла, как только вы узнаете результат.

check_prime = 1;

for ( y = 2; y <= num/2; y++)
{
if ( num % y == 0 )
{
check_prime = 0;
break;
}
}

В неудачном случае, когда все тестируемые вами числа являются простыми, это ничего не изменит, но если все (или почти все, при достаточно больших значениях, почти равных) являются составными, это сократит время выполнения на коэффициент не менее 5000

Следующее, что вы делите до num/2, Это не обязательно. Почему вы останавливаетесь на num/2и не в num - 1? Ну, потому что вы выяснили, что самый большой правильный делитель num не может быть больше чем num/2 потому что, если (num >) k > num/2, затем 2*k > num а также num не кратно k,

Это хорошо, не все это видят.

Но вы можете продолжить этот ход мыслей дальше. Если num/2 является делителем num, это означает num = 2*(num/2) (с использованием целочисленного деления, за исключением num = 3). Но потом num является четным, и его сложность уже была определена делением на 2, поэтому деление на num/2 никогда не будет судить, если это удастся.

Итак, каков следующий возможный кандидат на самый большой делитель, который необходимо рассмотреть? num/3 конечно. Но если это делитель num, затем num = 3*(num/3) (Если не указано num < 9) и деление на 3 уже решило вопрос.

Продолжай, если k < √num а также num/k является делителем num, затем num = k*(num/k) и мы видим, что num имеет меньший делитель, а именно k (возможно, даже меньшие).

Так наименьший нетривиальный делитель num меньше или равно √num, Таким образом, цикл нужно запустить только для y <= √num, или же y*y <= num, Если в этом диапазоне не было найдено делителя, num прост.

Теперь возникает вопрос, стоит ли зацикливаться

for(y = 2; y*y <= num; ++y)

или же

root = floor(sqrt(num));
for(y = 2; y <= root; ++y)

Первый требует одного умножения для условия цикла в каждой итерации, второй — для вычисления квадратного корня вне цикла.

Что быстрее?

Это зависит от среднего размера num и являются ли многие простыми или нет (точнее, на среднем размере наименьшего простого делителя). Вычисление квадратного корня занимает намного больше времени, чем умножение, чтобы компенсировать эту стоимость, цикл должен выполняться в течение многих итераций (в среднем) — зависит ли «многие» от 20, более 100 или более 1000, скажем, зависит. С num больше, чем 10^8, как, возможно, здесь, вероятно, лучший выбор — вычисление квадратного корня.

Теперь мы ограничили число итераций пробного цикла деления на √num будь то num является составным или простым и сокращает время работы как минимум в 5000 раз (при условии, что все m[index] > 0так что всегда num >= 10^8) независимо от того, сколько простых чисел входит в число проверенных чисел. Если большинство значений num Тэги — это композиты с небольшими простыми коэффициентами, коэффициент редукции значительно больше, и обычно время тестирования почти полностью используется для тестирования простых чисел.

Дальнейшее улучшение может быть достигнуто за счет уменьшения числа кандидатов делителей. Если num делится на 4, 6, 8, …, то он также делится на 2, поэтому num % y никогда не дает 0 даже y > 2, Это означает, что все эти подразделения являются лишними. С помощью специального кожуха 2 и увеличения числа делителей на этапы 2,

if (num % 2 == 0)
{
check_prime = 0;
} else {
root = floor(sqrt(num));
for(y = 3; y <= root; y += 2)
{
if (num % y == 0)
{
check_prime = 0;
break;
}
}
}

количество делений и время выполнения примерно наполовину (при условии, что достаточно плохих случаев, что работа для четных чисел незначительна).

Теперь, когда бы y кратно 3 (кроме самого 3), num % y будет вычисляться только тогда, когда num не является кратным 3, поэтому эти деления также являются лишними. Вы можете устранить их, также специальный корпус 3 и позволяя y пробегать только нечетные числа, которые не делятся на 3 (начните с y = 5, поочередно на 2 и 4). Это отрубает примерно треть оставшейся работы (если имеется достаточно плохих случаев).

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

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

root = floor(sqrt(num));
for(k = 0, y = primes[0]; k < prime_count && (y = primes[k]) <= root; ++k)
{
if (num % y == 0)
{
check_prime = 0;
break;
}
}

Если не самое большое значение num можно взять достаточно мало, если, например, вы всегда будете иметь num < 2^31затем вы должны найти простые числа к этому пределу в сите, чтобы вы могли посмотреть, num простое в постоянное время (сито 2 ^ 31 бит занимает 256 МБ, если у вас есть только флаги для нечетных чисел [нужен специальный регистр для проверки num чётно], вам нужно всего лишь 128 МБ, чтобы проверить простоту чисел < 2^31 в постоянное время возможно дальнейшее уменьшение необходимого пространства для сита).

Пока что для самого простого теста.

Если m массив содержит числа, делимые на 2 или на 5, может быть целесообразно переупорядочить циклы, иметь цикл для i самый внешний, и пропустите внутренние петли, если m[i] делится на 2 или на 5 — все остальные числа умножаются на степени 10 перед добавлением, поэтому num будет кратным 2 соотв. 5 и не премьер.

Но, несмотря на все это, выполнение кода все равно займет много времени. Девять вложенных циклов пахнут неправильным дизайном.

Что вы пытаетесь сделать? Может быть, мы можем помочь найти правильный дизайн.

// array m[] is assumed sorted in descending order      NB!
// a macro to skip over the duplicate digits
#define I(x) while( x<25 && m[x+1]==m[x] ) ++x;
for( a=1; a <= 25; a++) {
num1 = m[a]*100000000;
for( b=1; b <= 25; b++) if (b != a) {
num2 = num1 + m[b]*10000000;
for( c=1; c <= 25; c++) if (c != b && c != a) {
num3 = num2 + m[c]*1000000;
for( d=1; d <= 25; d++) if (d!=c && d!=b && d!=a) {
num4 = num3 + m[d]*100000;
for( e=1; e <= 25; e++) if (e!=d && e!=c && e!=b && e!=a) {
num5 = num4 + m[e]*10000;
for( f=1; f <= 25; f++) if (f!=e&&f!=d&&f!=c&&f!=b&&f!=a) {
num6 = num5 + m[f]*1000;
limit = floor( sqrt( num6+1000 ));   ///
for( g=1; g <= 25; g++) if (g!=f&&g!=e&&g!=d&&g!=c&&g!=b&&g!=a) {
num7 = num6 + m[g]*100;
for( h=1; h <= 25; h++) if (h!=g&&h!=f&&h!=e&&h!=d&&h!=c&&h!=b&&h!=a) {
num8 = num7 + m[h]*10;
for( i=1; i <= 25; i++) if (i!=h&&i!=g&&i!=f&&i!=e&&i!=d
&&i!=c&&i!=b&&i!=a) {
num = num8 + m[i];
if( num % 2 /= 0 && num % 3 /= 0 ) {
is_prime = 1;
for ( y=5; y <= limit; y+=6) {
if ( num %  y    == 0 ) { is_prime = 0; break; }
if ( num % (y+2) == 0 ) { is_prime = 0; break; }
}
if ( is_prime ) { return( num ); } // largest prime found
}I(i)}I(h)}I(g)}I(f)}I(e)}I(d)}I(c)}I(b)}I(a)}