Модификация простого числа сито в C

Question

Существует множество реализаций Решета Эратосфена онлайн.Посредством поиска в Google я нашел эту реализацию в C .

#include <stdio.h>
#include <stdlib.h>

#define limit 100 /*size of integers array*/ 

int main(){
    unsigned long long int i,j;
    int *primes;
    int z = 1;

    primes = malloc(sizeof(int) * limit);  

    for (i = 2;i < limit; i++)
        primes[i] = 1;

    for (i = 2;i < limit; i++)
        if (primes[i])
            for (j = i;i * j < limit; j++)
                primes[i * j] = 0;

    printf("\nPrime numbers in range 1 to 100 are: \n");
    for (i = 2;i < limit; i++)
        if (primes[i])
            printf("%d\n", i);

return 0;
}

Затем я попытался обновить существующий код, чтобы программа на C следовала тому, что описано Скоттом Риджуэем в * 1006.* Параллельные научные вычисления .В первой главе автор описывает то, что известно как сито простого числа.Вместо того, чтобы находить простые числа до числа k, модифицированное сито ищет простые числа между k <= n <= k ^ 2.Ridgway предоставляет псевдокод для написания этого алгоритма. </p>

Чтобы соответствовать псевдокоду, предоставленному автором, я изменилоригинальная программа выше и написала

#include <stdio.h>
#include <stdlib.h>

#define limit 10 /*size of integers array*/

int main(){
    unsigned long long int i,j,k;
    int *primes;
    int *arr[100];
    int z = 1;

    primes = malloc(sizeof(int) * limit);

    for (i = 2;i < limit; i++)
        primes[i] = 1;

    for (i = 2;i < limit; i++)
        if (primes[i])
            for (j = i;i * j < limit; j++)
                primes[i * j] = 0;

    /* Code which prints out primes for Sieve of Eratosthenes */
    /*printf("\nPrime numbers in range 1 to 100 are: \n");

    for (i = 2;i < limit; i++)
        if (primes[i])
            //printf("Element[%d] = %d\n", i, primes[i]);*/

    for (k=limit; k < limit*limit; k++)
        for (j = primes[0]; j = arr[sizeof(arr)/sizeof(arr[0]) - 1]; j++)
            if ((k % j) == 0)
                arr[k]=0;
        arr[k] = 1;

    printf("\nPrime numbers in range k to k^2 are: \n");
    for (k=limit; k < limit*limit; k++)
        if (arr[k])
            printf("Element[%d] = %d\n", k, k);

return 0;

}

, которая возвращает

Prime numbers in range k to k^2 are:
Element[10] = 10
Element[14] = 14
Element[15] = 15
Element[16] = 16
Element[17] = 17
Element[18] = 18
Element[19] = 19
.
.
.

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

как

for (k=limit; k < limit*limit; k++)
            for (j = primes[0]; j = arr[sizeof(arr)/sizeof(arr[0]) - 1]; j++)
                if ((k % j) == 0)
                    arr[k]=0;
            arr[k] = 1;

Поскольку я новичок в C,Я, вероятно, сделал элементарную ошибку.Я не уверен, что не так с пятью строками кода выше, и поэтому задал вопрос о переполнении стека.

Answer 1

У вас проблемы с оператором цикла, переменная j должна использоваться для индекса primes, который является указателем на массив int с 0 или 1 значениями.Вы можете использовать массив primes в этом случае S (k) в алгоритме.

for (k=limit; k < limit*limit; k++)
        for (j = primes[0]; j = arr[sizeof(arr)/sizeof(arr[0]) - 1]; j++)
            if ((k % j) == 0)
                arr[k]=0;
        arr[k] = 1;

Таким образом, цикл for с j должен быть

for (j = 2; j < limit; j++)

И условие IN if оператор должен быть

if (primes[j] && (k % j) == 0)
{
    arr[k] = 0;
    break;
}

И если это условиеэто правда, мы должны выйти из цикла for для переменной j.За пределами цикла с j следует проверить значение переменной j, чтобы проверить, завершен ли внутренний цикл или нет (j == limit).

if (j == limit) arr[k] = 1;

Итак, вот весь цикл for (внешний и внутренний цикл), который я модифицировал.

for (k = limit; k < limit*limit; k++)
{
    for (j = 2; j < limit; j++)
    {
        if (primes[j] && (k % j) == 0)
        {
            arr[k] = 0;
            break;
        }
    }
    if (j == limit) arr[k] = 1;
}

А вот и все решение:

#include <stdio.h>
#include <stdlib.h>

#define limit 10 /*size of integers array*/

int main() {
    unsigned long long int i, j, k;
    int *primes;
    int arr[limit*limit];
    int z = 1;

    primes = (int*)malloc(sizeof(int) * limit);

    for (i = 2; i < limit; i++)
        primes[i] = 1;

    for (i = 2; i < limit; i++)
        if (primes[i])
            for (j = i; i * j < limit; j++)
                primes[i * j] = 0;

    /* Code which prints out primes for Sieve of Eratosthenes */
    /*printf("\nPrime numbers in range 1 to 100 are: \n");

    for (i = 2;i < limit; i++)
        if (primes[i])
            //printf("Element[%d] = %d\n", i, primes[i]);*/

    for (k = limit; k < limit*limit; k++)
    {
        for (j = 2; j < limit; j++)
        {
            if (primes[j] && (k % j) == 0)
            {
                arr[k] = 0;
                break;
            }
        }
        if (j == limit) arr[k] = 1;
    }

    printf("\nPrime numbers in range k to k^2 are: \n");
    for (k = limit; k < limit*limit; k++)
        if (arr[k] == 1)
            printf("Element %d\n",  k);

    return 0;

}