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

Битовое решето Эратосфена: Исправить второй цикл, чтобы уменьшилось время работы программы

24.05.2015, 00:59. Просмотров 410. Ответов 1
Метки нет (Все метки)

Доброго времени суток! Подскажите, пожалуйста, как исправить второй цикл, чтобы уменьшилось время работы программы (на данном этапе при входном числе 10^9 считает 21 секунду, а нужно за 1 секунду).
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
  
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
char a[125000000];
int main()
{
long N;
int i = 0;
scanf_s("%d", &N);
a[0] = 172;
for (i = 8; i < N + 1; i += 8)
    a[i / 8] = 170;
 
 
clock_t time;
time = clock();
 
long k = 3;
for ( ; k * k <= N; k++)
{
    if (a[k / 8] & (1 << (k % 8)))
        for (i = k * k; i <= N; i += k)
            a[i / 8] &= ~(1 << (i % 8));
}
int c = 0;
for (i = 2; i < N + 1; i++)
if (a[i/8] & (1 << (i % 8))) c++;
 
printf("%d", c);
 
time = clock() - time;
printf(" %f", (double)time / CLOCKS_PER_SEC);
 
return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.05.2015, 00:59
Ответы с готовыми решениями:

Решето Эратосфена
Добрый день!помогите пожалуйста найти ошибку.код состоит из трех файлов.в первом из...

Не удается реализовать Решето Эратосфена
задача: быстро найти простые числа. проблема в том, что в СИ разбираюсь плохо ( так что код может...

Решето Эратосфена (работает некорректно)
вроде компилируется однако не работает корректно #include&lt;stdio.h&gt; int main() { int...

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

Нахождение первых пятиста простых чисел через решето Эратосфена
На языке си

1
Catstail
Модератор
24159 / 12148 / 2178
Регистрация: 12.02.2012
Сообщений: 19,727
24.05.2015, 11:00 2
Первый совет: деление k/8 заменить правым сдвигом на 3 разряда, остаток k%8 - заменить логическим умержением k & 7
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2015, 11:00

Получить все простые числа I, удовлетворяющие неравенству, используя решето Эратосфена
Даны натуральные числа К, Ь (К &lt; Ь). Получить все простые числа I, удовлетворяющие неравенству: К &lt;...

Время работы программы на Си
Работая на Lunux, время выполнения программы можно провериться с помощь комманды time т.е. вызвать...

Разработать структурную схему программы - Решето Эратосфена
У меня есть также блок-схема к паскалю......но мне требуется сделать структурную схему программы к...


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

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

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