Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Pinkolik
0 / 0 / 0
Регистрация: 30.05.2015
Сообщений: 14
1

Найти простые числа по порядку и записать их в файл, начиная с последнего записанного в файле

28.05.2016, 13:45. Просмотров 388. Ответов 5
Метки нет (Все метки)

Здравствуйте! Написал программу, которая ищет простые числа по порядку и записывает их в файл, начиная с последнего записанного в файле. Алгоритм проверки простых чисел взял из этой статьи https://habrahabr.ru/post/205318/ . Изменил лишь функцию возведения в степень по модулю (вместо рекурсии цикл, а вместо проверки на нечётность и деления на два - битовые операции), а функцию умножения по модулю убрал совсем, потому что она очень медленная. Вот, собственно, сам код
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <limits.h>
#include <time.h>
 
unsigned long long gcd(unsigned long long a, unsigned long long b)
{
    if (b == 0)
        return a;
    gcd(b, a%b);
}
 
 
 
unsigned long long binpow(unsigned long long a, unsigned long long n, unsigned long long m)
{
    unsigned long long res;
    res=1;
    while (n)
    {
        if (n & 1)
        {
            res=(res*a)%m;
            n--;
        }
        a=(a*a)%m;
        n >>= 1;
    }
    return res;
}
 
char simple(unsigned long long x)
{
    if (x == 2)
        return 1;
    srand(time(NULL));
    int i;
    unsigned long long a;
    for(i=0; i<100; i++)
    {
        a=(rand()%(x-2)) + 2;
        if (gcd(a,x) != 1)
            return 0;
        if (binpow(a, x-1, x) != 1)
            return 0;
    }
    return 1;
}
 
unsigned long long getlast(void)
{
    unsigned long long a1;
    FILE *fp;
    int i, k;
    char ch;
    fp=fopen("primes.txt", "r");
    i=-3;
    k=0;
    do
    {
        fseek(fp, i, SEEK_END);
        ch=fgetc(fp);
        i--;
        if (ch == '\n')
        {
            k++;
            i--;
        }
    }while(k != 1);
    fscanf(fp, "%llu\n", &a1);
    printf("%llu\n", a1);
    return a1;
}
 
int main(void)
{
    unsigned long long n, i;
    FILE *fp;
    fp=fopen("primes.txt", "a");
    n=ULLONG_MAX;
    for(i=getlast()+2; i<=n; i+=2)
    {
        if (simple(i)==1)
            fprintf(fp, "%llu\n", i);
    }
    fclose(fp);
    return 0;
}
И проблема заключается в том, что начиная с числа 4,312,952,827, программа перестаёт определять простые числа.
Немного поразбиравшись, я выяснил, что всё дело как раз в возведении в степень по модулю. Похоже, что на каком-то из умножений, переменная переполняется, из-за чего и выдаётся неправильный результат.
Тогда я заменил умножение аналогичной возведению в степень функцией. И всё заработало, но теперь возникла другая проблема: программа стала очень медленной. Для сравнения: в файл, в который писала программа без бинарного умножения по модулю, за минуту набегало около 7мб, а в файл, в который писала программа с ним, всего лишь 340кб.
Не зная, как выйти из данного положения, я решил обратиться на форум. Как же мне решить данную задачу, чтобы не было убытков ни в скорости, ни в правильности? Заранее спасибо за помощь
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.05.2016, 13:45
Ответы с готовыми решениями:

Определить минимальный элемент массива, записанного в файле. Результат записать в новый файл
Определить минимальный элемент массива, записанного в файле. Результат записать в новый файл. Для...

Сложить все цифры записанного в файле числа и результат занести в другой файл
Нужно решить эту задачу: Есть файл(например input.txt) в нем число(например 1021) Нужно прибавить...

Найти в файле минимальное и максимальное числа и записать их в файл (Найти ошибку)
В файле input.txt записаны числа, сколько их – неизвестно. Найти минимальное и максимальное числа и...

Заменить элементы последнего столбца матрицы A(4, 4) по порядку, начиная с 1-го, числами 1, 3, 5, 9
Помогите люди добрые! Завтра сдавать, а я маягко говоря не шарю, прошу профессионалов выручить...

Записать в файл последовательного доступа N действительных чисел. Найти разность первого и последнего числа этого файла
Не понимаю как считывать данные из файла и записывать их в переменные

5
NoMasters
Псевдослучайный
1912 / 1123 / 90
Регистрация: 13.09.2011
Сообщений: 3,182
28.05.2016, 15:13 2
Если вам нужен список абсолютно всех простых чисел(и только их) до какого-то предела, то вероятностные методы не подходят.
А код стоило бы хотя бы работоспособный выложить.
0
Pinkolik
0 / 0 / 0
Регистрация: 30.05.2015
Сообщений: 14
28.05.2016, 15:18  [ТС] 3
Цитата Сообщение от NoMasters Посмотреть сообщение
Если вам нужен список абсолютно всех простых чисел(и только их) до какого-то предела, то вероятностные методы не подходят.
А код стоило бы хотя бы работоспособный выложить.
Код работоспособный, забыл упомянуть, что перед тем как запустить программу, нужно создать файл "primes.txt", в котором написать "2"<enter>"3"<enter>, чтобы программа могла взять последнее число из файла. Не думал, что это имеет отношение к делу. Поясните, почему вероятностные методы не подходят? И если не подходят, то какими Вы посоветуете пользоваться?
0
NoMasters
Псевдослучайный
1912 / 1123 / 90
Регистрация: 13.09.2011
Сообщений: 3,182
28.05.2016, 18:25 4
Цитата Сообщение от Pinkolik Посмотреть сообщение
Код работоспособный
Ну да, а утерянные ретурны — это мелочи.
Цитата Сообщение от Pinkolik Посмотреть сообщение
Поясните, почему вероятностные методы не подходят? И если не подходят, то какими Вы посоветуете пользоваться?
Потому, что они вероятностные, собственно. Если проверки проходят, это ещё не значит, что число гарантированно простое. Увеличение количества проверяемых вариантов увеличивает шансы и часто их вполне достаточно для практического применения, но если нужен именно гарантированный список, нужны точные методы.
В статье, на которую вы ссылаетесь, есть ссылка на решето Эратосфена, этот как раз-таки точный метод. Увы, чем большие числа нужны, тем медленнее будет работать, но здесь уже ничего не поделаешь.
0
Pinkolik
0 / 0 / 0
Регистрация: 30.05.2015
Сообщений: 14
28.05.2016, 18:35  [ТС] 5
Хорошо, спасибо, про решето Эратосфена я позже почитаю, сейчас мне более интересно, как мне нужно модифицировать функцию binpow, чтобы она исправно работало на больших числах, при этом не проиграв в скорости?
0
Pinkolik
0 / 0 / 0
Регистрация: 30.05.2015
Сообщений: 14
30.05.2016, 22:05  [ТС] 6
Читал, пытался осмыслить, но для меня это решето Эратосфена совсем не ясно. Хотелось бы всё таки старым способом попробовать, мне даже не важно достоверно оно простое или нет, я делаю это просто ради интереса)
0
30.05.2016, 22:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.05.2016, 22:05

Найти в текстовом файле все отрицательные числа и записать их в другой файл
Всем добрый день!) нужна помощь в решении одной задачки...плиззз:) В текстовом файле FileIn...

Записать в текстовый файл все простые числа до заданного числа
1. Дано целое число от 2 до 1000. Программа определяет и записывает в текстовый файл все простые...

В файле есть буквы и цифры. В другой файл записать числа из этого текста и найти их сумму
Здравствуйте! Есть задачка: В файле есть текст - буквы и цифры. В другой файл надо записать числа...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru