C - Вывести все простые числа от 1 до 100, используя массивы

Question

ОК, поэтому я получил эту задачу, где мне нужно распечатать все простые числа от 1 до 100 ... Однако в моем коде есть ошибка, которую я не могу найти. Вот как я думал, что проблема должна быть решена:Для любого числа от 3 до 100 проверьте, есть ли какое-либо другое число в массиве простых чисел, которое оно делит. Если число не простое ... Если нет, то число простое и должно быть добавлено в массив.просто, правда?Однако ... не работает .. Вот мой код:

#include <stdio.h>

int main()
{
    int Primes[50] = {0};
    int i,j,k;

    Primes[0]=2;
    Primes[1]=3;
    for(i=3;i<101;i++)
    {
        for(j=2;j<100;j++)
        {
            if(i % Primes[j] != 0 && Primes[j] !=0)
            {
                Primes[j]=i;
            }
        }
    }
    printf("Primes array : \n");
    for(k=0;k<51;k++)
    {
        printf("%d ", Primes[k]);
    }
    return 0;
}

Answer 1

Есть много проблем в алгоритме, который вы использовали.Используйте эту простую версию с проблемами, указанными в коде.

int main(void){

        int Primes[50] = {0};
        int i,j,k = 0 /* use for prime count purpose */;
        Primes[0]=2;
        Primes[1]=3;
        for(i=4 /* 3 is already stored */; k != 48; i++) { /* rotate loop until prime count doesn't reaches 48 */
                for(j = 2; j<=i; j++) { /* i is the number you want to check whether its prime or not. SO rotate loop from 2 to "i" */
                        if(i % j == 0){ /* use i%j not i % Primes[j] as you want to check whether i is prime or not */
                                if(i == j)  /* if its a prime numbur j reaches upto i */
                                        Primes[k++]=i; /* store it */
                                break; /* comes out of inner loop */
                        }
                }
        }
        printf("Primes array : \n");
        for(int index = 0;index < k; index++) { /* rotate k times not some random 51 times */
                printf("%d ", Primes[index]);
        }
        return 0;
}

Answer 2

Когда вы делаете это:

        if(i % Primes[j] != 0 && Primes[j] !=0)
        {
            Primes[j]=i;
        } 

Вы говорите: «Если текущее число не делится на данное простое число, замените данное простое число на текущее число».Это не то, что вы хотите.

Вам необходимо проверить, не делится ли текущее число на любое простое число.Таким образом, вам нужно зациклить список простых чисел, чтобы убедиться, что ваш номер не делится ни на один из них, и, если это так, добавить число в конец списка.Вы можете сделать это следующим образом:

int num_primes = 0;

for (i=2;i<101;i++)
{
    int is_prime = 1;
    for(j=0; j<num_primes && is_prime; j++)
    {
        if(i % Primes[j] == 0)
        {
            is_prime = 0;
        }
    }
    if (is_prime) {
        Primes[num_primes++] = i;
    }
}

В приведенном выше коде мы используем num_primes для подсчета числа простых чисел, которые у нас есть, и is_prime, чтобы увидеть, нашли ли мы простое число, которое делиттекущий номер.Когда вы делите каждое число на простое число, если остаток равен 0, вы знаете, что число не простое, и установите is_prime в 0. Это также приводит к немедленному выходу из внутреннего цикла.Затем, если is_prime все еще установлен в конце внутреннего цикла, у вас есть простое число, и вы добавляете его в конец списка.

У вас также есть ошибка «по одному» при печатицикл:

for(k=0;k<51;k++)

Поскольку Primes имеет размер 50, самый большой допустимый индекс - 49. Поэтому измените его на:

for(k=0;k<50;k++)