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

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

Войти
Регистрация
Восстановить пароль
 
Olia88
1 / 1 / 0
Регистрация: 20.02.2012
Сообщений: 24
#1

Нахождение чисел меньше N числа Марсена - C++

12.04.2012, 11:05. Просмотров 613. Ответов 1
Метки нет (Все метки)

Дано натуральное число N. Найти все меньше n числа Марсена( Числа Марсена - это числа (2^p)-1, где p простое число) p не вводится, нужно считать в цикле
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2012, 11:05     Нахождение чисел меньше N числа Марсена
Посмотрите здесь:
Найти сумму чисел Фибоначчи меньше заданного числа Q C++
Определить сумму последовательности чисел, которые меньше заданного числа C++
C++ Вывести количество чётных чисел Фибоначчи меньше заданного числа
Вывести квадраты натуральных чисел, которые меньше указаного числа C++
C++ Нахождение простых чисел до заданого числа n
Вычислить количество вводимых чисел пока их сумма меньше заданного числа C++
Найти n первых простых чисел, сумма цифр у которых меньше заданного числа C++
Рекурсивная функция: вычисление суммы чисел Фибоначчи, пока они меньше введенного числа C++
Выдать пары простых чисел, разность между которыми равна 4, а сами числа меньше n C++
Нахождение пар чисел равныхпроизведению заданного числа( одномерный массив) C++
C++ Дана последовательность из целых чисел. Все элементы меньше заданного числа, увеличить в два раза
Разделить массив действительных чисел на два списка, в первом числа меньше заданного, во втором - больше C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
12.04.2012, 11:36     Нахождение чисел меньше N числа Марсена #2
Для начала, найдем pmax.
2p-1<=N
2p<=N+1
p<=log2(N+1).
pmax=[log2(N+1)]
Теперь задача свелась к нахождению всех простых чисел не больше pmax.
Приведу не очень экономичный по оперативке\вычислению вариант -- очень экономичных не знаю:
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
int n=pmax/2;
int* s=new int[n];
for(int i=0; i<n; i++)
s[i]=0;
s[0]=2;
for(int i=3; i<=pmax; i++)
{
   bool flag=false;
   int j=0;
   while(s[j]!=0)
   {
      if(i%s[j]==0)
      {
         flag=true;//Поделилось нацело -- число не простое
         break;
      }
      j++;
   }
   if(flag==false)
   {
   int j=0;
   while(s[j]!=0)
   j++;
   s[j]=i;
}
int j=0;
while(s[j]!=0)
j++;
n=j;
int* smp=new int[n];
for(int i=0; i<n; i++)
smp[i]=s[i];//Массив простых чисел
delete s;
А далее уже по формуле 2p-1 считаем числа Марсена
Yandex
Объявления
12.04.2012, 11:36     Нахождение чисел меньше N числа Марсена
Ответ Создать тему
Опции темы

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