Форум программистов, компьютерный форум CyberForum.ru

простые числа до миллиарда - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
Starbucks
0 / 0 / 0
Регистрация: 06.12.2012
Сообщений: 6
07.12.2012, 00:27     простые числа до миллиарда #1
помогите написать программу на зачёт

программа должна считать все простые числа до миллиарда менее чем за 3 минуты (максимум пять)
используя решето Аткина или Эратосфена (не обязательно)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.12.2012, 00:27     простые числа до миллиарда
Посмотрите здесь:

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p. C++
C++ Даны целые числа р и q. Получить все делители числа q, взаимно простые с р
Даны целые числа р и q. Получить все делители числа q, взаимно простые с р. C++
C++ Даны натуральные числа a,b(a<= Ь). Получить все простые числа р, удовлетворяющие неравенствам a<= р<= b.
C++ Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NoMasters
Псевдослучайный
1737 / 1080 / 69
Регистрация: 13.09.2011
Сообщений: 3,093
07.12.2012, 01:57     простые числа до миллиарда #2
У меня тут как раз завалялось в загашниках... Принимает потолок расчёта и место, куда положить указатель на полученный массив, возвращает количество найденных чисел. На моём унылом ноутбучном кордвадубе расчёт до миллиона проходит за две минуты.
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
int prime(int max, int **out_arr)
{
    int i, t, l_alive, f_alive, count;
    int *p_arr;
    int *all;
    
    all = malloc((max + 2) * sizeof(int));
    
    for(i = 1; i <= max + 1; ++i)
    {
        all[i] = i + 1;
    }
    
    count = 0;
    t = 1 + 1;
    l_alive = 2;
    f_alive = 2;
    while(t <= max)
    {
        i = t + 1;
        while(i <= max)
        {
            if(i % t)
                l_alive = i;
            else
                all[l_alive] = all[i];
            i = all[l_alive];
        }
        t = all[f_alive];
        f_alive = t;
        ++count;
    }
    p_arr = malloc(sizeof(int) * count);
    t = 2;
    for(i = 0; i < count; ++i)
    {
        p_arr[i] =  t;
        t = all[t];
    }
    free(all);
    *out_arr = p_arr;
    return count;
}
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11822 / 6801 / 769
Регистрация: 27.09.2012
Сообщений: 16,869
Записей в блоге: 2
Завершенные тесты: 1
07.12.2012, 09:16     простые числа до миллиарда #3
Быстрая проверка натурального числа на простоту
Starbucks
0 / 0 / 0
Регистрация: 06.12.2012
Сообщений: 6
07.12.2012, 15:21  [ТС]     простые числа до миллиарда #4
ругается 2010 студио error C2440: =: невозможно преобразовать "void *" в "int *"
Для преобразования "void*" к указателю на тип, не являющемуся "void", требуется явное приведение

all = malloc((max + 2) * sizeof(int));
p_arr = malloc(sizeof(int) * count);

вот в этих двух строчках
Starbucks
0 / 0 / 0
Регистрация: 06.12.2012
Сообщений: 6
08.12.2012, 23:53  [ТС]     простые числа до миллиарда #5
ругается 2010 студио error C2440: =: невозможно преобразовать "void *" в "int *"
Для преобразования "void*" к указателю на тип, не являющемуся "void", требуется явное приведение

all = malloc((max + 2) * sizeof(int));
p_arr = malloc(sizeof(int) * count);

вот в этих двух строчках
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
09.12.2012, 00:13     простые числа до миллиарда #6
нет, здесь нужно не то. Вам нужно решето Эратосфена, со сложностью O (n log log n);
http://e-maxx.ru/algo/eratosthenes_sieve

Добавлено через 2 минуты
хм... а хотя памяти может не хватить - смотря какая реализация решета. Я как-то делал такое, до миллиарда прошло довольно быстро - менее 10 минут.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
09.12.2012, 00:36     простые числа до миллиарда #7
Starbucks, нужно найти количество простых чисел или выдать массив простых чисел?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.12.2012, 00:53     простые числа до миллиарда
Еще ссылки по теме:

C++ Одномерный массив. Вывести на экран все числа, индексы которых есть простые числа.
C++ Дано натуральное число. Вывести на экран все простые числа до заданного числа.
Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p C++

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

Или воспользуйтесь поиском по форуму:
Starbucks
0 / 0 / 0
Регистрация: 06.12.2012
Сообщений: 6
09.12.2012, 00:53  [ТС]     простые числа до миллиарда #8
надо выдать список, содержащий все простые числа
Yandex
Объявления
09.12.2012, 00:53     простые числа до миллиарда
Ответ Создать тему
Опции темы

Текущее время: 00:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru