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

Question

ghost_101 @ghost_101

студент-первак

C

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

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

#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;


}

Вопрос задан более трёх лет назад
93 просмотра

5 комментариев

Подписаться 1 Простой 5 комментариев

Roman @myjcom

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 @wisgest

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

Написано более трёх лет назад
crazywu @crazywu

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

Написано более трёх лет назад

ghost_101 @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 @crazywu

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

Написано более трёх лет назад

Пригласить эксперта

Ответы на вопрос 1

Комментировать

Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации

Похожие вопросы

C

+1 ещё

Простой
Как отправить запрос на терминал Vendotek?
- 2 подписчика
- вчера
- 170 просмотров
0

ответов
C++

+2 ещё

Средний
Как сделать маштабирование относительно центра экрана?
- 1 подписчик
- вчера
- 64 просмотра
0

ответов
C

+1 ещё

Простой
Как вывести значение указателя без иннициализации?
- 1 подписчик
- 12 апр.
- 104 просмотра
4

ответа
C

+1 ещё

Простой
Можно использовать файл .ino для работы на устройствах Orange pi?
- 1 подписчик
- 11 апр.
- 54 просмотра
2

ответа
C

Простой
Как из массива байтов HEX сделать сделать DEC?
- 1 подписчик
- 09 апр.
- 92 просмотра
2

ответа
C

+1 ещё

Простой
Доступ к массиву объявленному в ассемблере из Си?
- 2 подписчика
- 09 апр.
- 985 просмотров
1

ответ
C

Средний
Как устранить ошибку конверсии при использовании битовых полей?
- 3 подписчика
- 08 апр.
- 793 просмотра
3

ответа
C

Простой
Почему передается некорректный адрес указателя в функцию?
- 1 подписчик
- 06 апр.
- 57 просмотров
1

ответ
C

Средний
Как исправить предупреждение о конверсии в макросе?
- 3 подписчика
- 05 апр.
- 721 просмотр
1

ответ
C

Простой
Как следать процерку на ввод целых чисел?
- 1 подписчик
- 26 мар.
- 119 просмотров
3

ответа
Показать ещё Загружается…

Программист C для Embedded Linux

Radiofid • Санкт-Петербург

от 120 000 до 180 000 ₽

Разработчик C/C++ c GStreamer/Deepstream

Передовая Инженерная Школа МФТИ

До 250 000 ₽

Программист C/C++ embedded Linux

РТК Автоматика • Москва

от 170 000 до 250 000 ₽

Доработать клиентское приложение для GTA 5 на C#

20 апр. 2024, в 00:51

1000 руб./за проект

Верстка и логика формы выбора билетов в зале для покупки

20 апр. 2024, в 00:43

10000 руб./за проект

Разработать формирование УПД на Java

20 апр. 2024, в 00:28

20000 руб./за проект

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...
В весь код не вникал, но функция IsItSimple() уже как бы намекает, что решето Эратосфена здесь не при чём. (А если при чём, то она не нужна. Совсем.)
wisgest, зря не вникали, реализация, конечно, вызывает вопросы, но решето там все же присутствует, просто для чего-то создана доп проверка)
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; }

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

Answer 1 · 2019-09-30 17:21:42

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

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

Войдите, чтобы написать ответ

Минуточку внимания

Войдите на сайт