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

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

Войти
Регистрация
Восстановить пароль
 
Dangelo
7 / 7 / 1
Регистрация: 28.11.2010
Сообщений: 57
#1

Простые числа. - C++

12.12.2010, 03:50. Просмотров 650. Ответов 1
Метки нет (Все метки)

Доброй ночи. Есть вот такое задание
Исходные данные
В первой строке находится ровно одно целое число k, задающее количество чисел в списке. За ним следуют k целых чисел, по одному в строке. Все числа положительные и не превосходят 15000.
Результат
Для каждого числа n из списка вы должны вывести n-е по счёту простое число. Ответ для каждого числа должен находиться в отдельной строке.
Пример
исходные данные результат
4 5
3 3
2 11
5 17
7

и такой код:
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
#include "stdafx.h"
#include <stdio.h>
unsigned  int t[170000];
unsigned int o=170000;
void mass();
void prost (int p);
void main()
{
    int k, n[15001], p;
    scanf ("%d", &k);
    for (int i=0; i<k; i++)
    {
        scanf ("%d",&n[i]);
    }
    mass();
    for (int i=0; i<k; i++)
    {
        
        p=n[i];
        prost(p);
    }
    
    scanf("%d",&k);
}
void mass () //Функция вычисления простых чисел;
{
    int p=2, i2=2; 
    for (int i=2; i<=o; i++) //заполняем массив числами
    {
        t[i]=i;
    }
    
    
    while (p<o)  // Алгоритм Эратосфена
    {
        while (t[p]!=-1)
        {
            while ( (i2 * p) <= o)
            {
                t[i2*p]=-1; 
                i2++;
            }
            i2=2;
            p++;
        }
        p++;
    }
}
void prost (int p)
{
    int j=2;
    while (p)
    {
        if (t[j]!=-1)
        {
            p--;
        }
        j++;
    }
    printf ("%d\n",t[j-1]);
}
Вопрос: Как можно оптимизировать код для более быстрой работы?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2010, 03:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Простые числа. (C++):

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

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

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

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

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

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

1
valeriikozlov
Эксперт С++
4677 / 2503 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
12.12.2010, 07:45 #2
Вопрос: Как можно оптимизировать код для более быстрой работы?
Во первых, по моим подсчетам у Вас в массиве t[] находится всего 1756 первых простых чисел.
Во вторых, для каждого очередного числа в новой строке Вам приходится для нахождения простого числа искать его с самого начала массива t[].
Вся оптимизация должна будет заключаться в том что бы сделать изначально массив в котором только простые числа и найти тогда это число будет очень просто и самое главное быстро.
Алгоритм нахождения таким образом недавно обсуждался здесь:
Всё просто
Самый первый код volovzi реализует этот алгоритм.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2010, 07:45
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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