Поиск простых чисел с помощью решета Эратосфена. Почему идёт неправильный вывод и выдаёт ошибку?

Question

[ghost_101]

Необходимо найти в массиве, заданной длины, простые числа и вывести их на экран с помощью решета Эратосфена. Не могу понять, где ошибки. С динамическим массивом работаю впервые.

#include <stdio.h>
#include <malloc.h>


int IsItSimple(int N)
{
	for (int i = 2; i * i <= N; i++)  
		if (N % i == 0) {
			return 0;
		}
	return 1;
}

int main(void) {
	int* Array;
	int ArrLength, j = 1;
	scanf_s("%d", &ArrLength);

	Array = (int*)malloc(ArrLength * sizeof(int));

	for (int i = 0; i < ArrLength; i++) {
		Array[i] = i + 1;
	}

	while (j <= ArrLength) {
		if (IsItSimple(Array[j]) == 1 && Array[j] != 0) {
			int temp = j;
			while (temp <= ArrLength) {
				temp = temp + Array[j];
				Array[temp] = 0;
				
			}
		}
		j++;
	}


	for (int i = 1; i < ArrLength; i++) {
		if (Array[i] != 0) {
			printf("%d ", Array[i]);
		}
	}

	free(Array);

	return 0;


}

Comments

[Roman]

ghost_101,

выдаёт ошибку

https://ru.wikipedia.org/wiki/Ошибка_сегментации

#include <assert.h>
// ...
// В Си нет необходимости использовать приведение типа для malloc
// это не ошибка просто читается лучше.

Array = malloc(ArrLength * sizeof(int));

// ... 
while (temp < ArrLength) // ??? '<=' просто '<' индексация с 0
{
  temp = temp + Array[j];
  assert(temp < ArrLength); // add
  Array[temp] = 0;
}
// ...

а по алгоритму ---> https://vscode.ru/prog-lessons/poisk-prostyih-chis...

[wisgest]

В весь код не вникал, но функция IsItSimple() уже как бы намекает, что решето Эратосфена здесь не при чём. (А если при чём, то она не нужна. Совсем.)

[crazywu]

wisgest, зря не вникали, реализация, конечно, вызывает вопросы, но решето там все же присутствует, просто для чего-то создана доп проверка)

[ghost_101]

crazywu,

#include <stdio.h>
#include <malloc.h>

int main(void) {

	int* Array;
	int ArrayLength;

	scanf_s("%d", &ArrayLength);

	Array = (int*)malloc(ArrayLength * sizeof(int));

	for (int i = 0; i < ArrayLength; i++) {
		Array[i] = i + 1;
	}

	for (int i = 1; i * i <= ArrayLength; i++) {
		if (Array[i] != 0) {
			for (int j = i + Array[i]; j < ArrayLength; j += Array[i]) {
				Array[j] = 0;
			}
		}
	}

	for (int i = 1; i < ArrayLength; i++) {
		if (Array[i] != 0) {
			printf("%d ", Array[i]);
		}
	}

	free(Array);
	
	return 0;
}

В итоге реализовал так, поняв все ошибки. Проверка была действительно лишней.

[crazywu]

ghost_101, да, так выглядит значительно лучше

Answer 1

[crazywu]

Во-первых, согласно методу решета Эратосфена вам абсолютно ни к чему дополнительно проверять встретившееся в массиве не нулевое числа на простоту (функция IsItSimple).
Во-вторых, вы выделяете память в Array для ArrLength числа аргументов, но пытаетесь обращаться к ArrLenght+1 аргументу while (j <= ArrLength) т.к. используете j в качестве индекса, а индексы массива ведут отчет с 0.