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

С++ для начинающих

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

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

07.12.2012, 00:27. Просмотров 2228. Ответов 7
Метки нет (Все метки)

помогите написать программу на зачёт

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

Задача про простые числа. Выпишите все простые числа, находящиеся в интервале между а и б - C++
#include <stdio.h> #include <iostream> #include <conio.h> #include <math.h> using std::cout; using std::cin; using...

Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа - C++
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа. Простые числа это когда они делятся только...

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

Даны натуральные числа a,b(a<= Ь). Получить все простые числа р, удовлетворяющие неравенствам a<= р<= b. - C++
Даны натуральные числа a,b(a&lt;= Ь). Получить все простые числа р, удовлетворяющие неравенствам a&lt;= р&lt;= b. Решите на С++. Буду очень...

Даны целые числа р и q. Получить все делители числа q, взаимно простые с р - C++
Получить все делители числа q, взаимно простые с р.

Даны целые числа р и q. Получить все делители числа q, взаимно простые с р. - C++
Даны целые числа р и q. Получить все делители числа q, взаимно простые с р. Решите на С++. Заранее спасибо!

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
NoMasters
Псевдослучайный
1754 / 1097 / 72
Регистрация: 13.09.2011
Сообщений: 3,134
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;
}
0
Croessmah
Эксперт CЭксперт С++
13237 / 7509 / 847
Регистрация: 27.09.2012
Сообщений: 18,448
Записей в блоге: 3
Завершенные тесты: 1
07.12.2012, 09:16 #3
Быстрая проверка натурального числа на простоту
0
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);

вот в этих двух строчках
0
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);

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

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

Найти числа-близнецы: простые числа разность между которыми равна 2 - C++
Дано натуральное число n. Среди чисел n, n + 1, …, 2n найти все числа-близнецы: простые числа, разность между которыми равна 2.

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p. - C++
Даны натуральные числа p и q. Получить все делители числа q , взаимно простые к p.

Найти простые числа с суммой цифр меньше заданного числа - C++
нужно написать прогу, можно использовать только циклы. Если можно, с объяснениями. Условие: Найти n первых простых чисел, сумма цифр у...

Дано натуральное число. Вывести на экран все простые числа до заданного числа. - C++
Дано натуральное число. Вывести на экран все простые числа до заданного числа.


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
09.12.2012, 00:53
Ответ Создать тему
Опции темы

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