Segmentation fault(core dumped)?

Question

[szafranji]

Здравствуйте. Задача: для данного числа n, подсчитай к-ство простых чисел, меньших од n.
Пример:
Ввод:
10
Вывод:
4
//т.к. простые числа до 10: 2, 3, 5, 7.

Написал алгоритм решета Эратосфена, но почему-то мне для чисел больших 100 000 выдает segmentation fault(core dumped). Знаю, что такое сегфолт, но не понимаю, что в моем коде не так.

#include <stdio.h>

int main() {
	int n, count = 0;
	printf("");
	scanf("%d", &n);

	int *Arr = new int[n+1];
	for(int i = 0; i < n+1; i++) {
		Arr[i] = i;
	}

	for(int i = 2; i < n+1; i++) {
		if(Arr[i] != 0) {
			count++;
			for(int j = i*i; j < n+1; j += i) {
				Arr[j] = 0;
			}
		}
	}
	printf("%d\n", count);
        delete[] Arr;
	
}

Comments

[Модератор]

szafranji дорогой пользователь, настоятельно рекомендуем еще раз обратить самое пристальное внимание на п. 3.1 регламента работы сервиса (и, в особенности, на его последний абзац).
В противном случае ваши вопросы будут удаляться по причине тег-спама, а систематические нарушения приведут к блокировке учетной записи.

[szafranji]

Модератор, простите, впредь обещаю более ответственно подходить к выбору тегов

Answer 1

[15432]

У вас число i*i переваливает за MAXINT, j становится отрицательным (что удовлетворяет условию < n+1), происходит разыменование массива по некорректному индексу и сегфолт.

Используйте unsigned long long или long long хотя бы для j, как вариант.

Comments

[szafranji]

Спасибо, все верно.

Answer 2

[galaxy]

Вы используете знаковый тип для индексации (что само по себе плохо). Конкретно в это месте у вас при i ~ 46340 происходит переполнение знакового int и j становится отрицательным (сильно отрицательным: -2.14e9) и программа валится на присвоении Arr[j] = 0;
for(int j = i*i; j < n+1; j += i) {

Comments

[szafranji]

Спасибо, не заметил