Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/103: Рейтинг темы: голосов - 103, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 14.03.2017
Сообщений: 67
1

Наибольший простой делитель числа

26.10.2018, 12:05. Показов 19003. Ответов 6
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Всем привет! Есть программа для вычисление наибольшего простого делителя некоторого числа:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <stdlib.h>
 
int main ()
{
    long long n, p, del;
    scanf("%lld", &n);
    long long arr[n - 1];
    for (long long i = 0; i < n - 1; i++) 
    {
        arr[i] = i + 2;
    }
    for (long long i1 = 0; i1 < n - 1; i1++) 
    {
        if (i1 == 0) p = 2;
        else
        {
            for (long long i2 = p - 1; i2 < n - 1; i2++)
            {
                if (arr[i2] % p == 0) arr[i2] = 0;
            }
            for (long long i2 = p - 1; i2 < n - 1; i2++)
            {
                if (arr[i2] != 0)
                {
                    p = arr[i2];
                    break;
                }
            }
        }
    }
    for (long long i = 0; i < n - 1; i++)
    {
        if ((arr[i] != 0) && (n % arr[i] == 0)) del = arr[i];
    }
    printf("%lld", del);
}
Если ввести: 1874657754, программа вылетает с Segmentation fault 11.
Сижу 2 дня и не понимаю что не так.
Подскажите пожалуйста в чем ошибка.
Заранее спасибо)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.10.2018, 12:05
Ответы с готовыми решениями:

Наибольший простой делитель числа и Решето Эратосфена
Необходимо найти наибольший простой делитель числа &quot;n&quot;, используя решето Эратосфена. Программа...

Наибольший Простой Делитель решетом эратосфена
Здравствуйте. Выдали задание желающим реализовать поиск наибольшего простого делителя методом...

Даны натуральные числа X и Y. Вычислить их наибольший общий делитель
помогите пожалуйста составить программу.у меня есть примерный код,но в нем пользователь вводит 3...

Наибольший общий делитель
Наибольший общий делитель

6
Эксперт CЭксперт С++
5118 / 4558 / 854
Регистрация: 07.10.2015
Сообщений: 9,462
26.10.2018, 12:20 2
TheSava, Вам не кажется, что не стоит пытаться выделять в стеке 14.3 Гб?...
1
0 / 0 / 0
Регистрация: 14.03.2017
Сообщений: 67
26.10.2018, 14:25  [ТС] 3
liv, Спасибо! Понял(((
0
Диссидент
Эксперт C
27709 / 17325 / 3811
Регистрация: 24.12.2010
Сообщений: 38,979
27.10.2018, 10:59 4
Цитата Сообщение от liv Посмотреть сообщение
не стоит пытаться выделять в стеке 14.3 Гб?...
В самом деле эти страшные гигабайты и не будут выделяться. Выделится 8*n (mod 263) или что-то вроде того, но по модулю
TheSava, не можете в двух словах описать свой алгоритм? Неужели строите решето Эратосфена?
Хочу сказать, что существует значительно более компактный способ решения задачи. Без всяких массивов вообще. И довольно простой.
1
0 / 0 / 0
Регистрация: 14.03.2017
Сообщений: 67
28.10.2018, 14:54  [ТС] 5
Байт, К сожалению в задаче надо использовать решето Эратосфена( И я вот пытаюсь понять как это сделать))
0
Диссидент
Эксперт C
27709 / 17325 / 3811
Регистрация: 24.12.2010
Сообщений: 38,979
28.10.2018, 15:23 6
Цитата Сообщение от TheSava Посмотреть сообщение
в задаче надо использовать решето Эратосфена
Тогда надо его организовать правильно. На фига делать массив long long? Что ты там собираешься хранить? Номер элемента? Но он и так известен В самом деле там должна храниться одна логическая переменная со значениями false - true. То есть достаточно одного бита.
Если тебе пока трудно работать с битовыми массивами, возьми байтовый. char arr[n-1];
Но лучше с битовым. Тогда в один байт влезает информация о 8-ми числах. - выигрыш в 8 раз! И это не очень сложно, уверяю.
А если слегка поднатужиться, то можно догадаться как в одном байте (8 бит) хранить информацию о 30 числах. Выигрыш еще почти в 4 раза. Но это уже тема для другого разговора...

Добавлено через 3 минуты
Может быть найдешь что-то полезное для себя из этого объемного, но насыщенного информацией, топика
Быстрая проверка натурального числа на простоту
0
0 / 0 / 0
Регистрация: 14.03.2017
Сообщений: 67
28.10.2018, 17:26  [ТС] 7
Байт, Да, я как раз сейчас в процессе такого способа
0
28.10.2018, 17:26
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.10.2018, 17:26
Помогаю со студенческими работами здесь

Найти наибольший общий делитель
Найти наибольший общий делитель

Найти наибольший общий делитель
Заданные четыре натуральные числа a, b, c, d. Найти их наибольший общий делитель.(через функцию)

Найти наибольший общий делитель 8 чисел
Добрый вечер. Господа! Я не в состоянии написать программу сам, так как не понимаю как записать это...

Найти наибольший общий делитель трех чисел
Даны два натуральных числа A и B. Требуется найти их наибольший общий делитель (НОД). Входные...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru