Консультации Портала - Консультация #175151

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

Консультация № 175151

12.12.2009, 05:46

0.00 руб.

0 9 2

Компьютеры Программирование

зДРАВСТВУЙТЕ.. прошу помощь у экспертов в написании програмки на C++. Дано натуральное число n. Установить, является ли оно числом Мерсена (простое число называется числом Марсена, если оно равно 2^p-1, где p тоже натуральное число). Заранее благодарю. (если чо- chickencat@mail.ru)

Приложение:
Учусь я на 1 курсе в универе, поэтому прошу не делать программу сложной

Обсуждение

Неизвестный

12.12.2009, 14:36

общий

F®ost:
Error 2 error C4716: 'Mersen' : must return a value

Неизвестный

12.12.2009, 15:09

общий

Неизвестный

12.12.2009, 17:36

общий

chickencat:
Просто перепишите прототип функции Mersen() как

Код:

void Mersen(unsigned int power)

Да и поскольку Вы писали, что требуется попроще то функцию NumberToPower() разумнее переписать без рекурсии

Код:

unsigned long long NumberToPower(unsigned short number, unsigned int power)
{
	unsigned long long result=1;
	while(power--)
	{
		result*=number;
	}
	return result;
}

Умножать рекурсивно это извращение.

Неизвестный

12.12.2009, 17:57

общий

так как будет вся программа выглядеть с впиской

давно

lamed

Академик
320937
2216

12.12.2009, 21:56

общий

это ответ

Здравствуйте, chickencat. Существует два определения чисел Мерсенна.
1. Натуральное число, если оно равно 2^p-1, где p тоже натуральное число
2. Простое число, если оно равно 2^p-1, где p тоже простое число
Соответственно, в приложении две программы.
Идея вычисления в следующем. Прибавим единицу к тестируемому числу. Если это число Мерсенна, оно является степенью двойки, тогда создадим битовую маску и в цикле производим операцию побитового "И". В результате получим либо ноль, либо единицу. Если это степень двойки, должна быть одна единица в каком-то из разрядов, остальные нули. В варианте 2 необходимо еще проверить показатель степени.

Приложение:
#include <iostream>
using namespace std;

bool mersenn(unsigned long long int a);
int main()
{
unsigned long long a;
cout << "a=";
cin >> a;

cout << (mersenn(a)?"yes":"no")<< endl;
return 0;
}

bool mersenn(unsigned long long int a)
{
const unsigned long long int digit=1;
int c=0;
a++;

for (unsigned short int i=0; i<sizeof(a)*8; i++)
{
if (static_cast<unsigned long long int>(a&digit<<i)!=0)
c++;
if (c>1)
return false;
}
return (c==1);
}

/***************************/

#include <iostream>
using namespace std;

bool isprime(unsigned long long int a);

bool prime_mersenn(unsigned long long int a);
int main()
{
unsigned long long a;
cout << "a=";
cin >> a;

cout << (isprime(a)&&prime_mersenn(a)?"yes":"no")<< endl;
return 0;
}

bool prime_mersenn(unsigned long long int a)
{
const unsigned long long int digit=1;
int c=0;
a++;

for (unsigned short int i=0; i<sizeof(a)*8; i++)
{
if (static_cast<unsigned long long int>(a&digit<<i)!=0)
{
c++;
if (!isprime(i))
return false;
}
if (c>1)
return false;
}
return (c==1);
}

bool isprime(unsigned long long int a)
{
if (a==2)
return true;
else if (a%2==0)
return false;
unsigned long long int divisor = 3;
while (divisor*divisor<=a)
{
if (a%divisor ==0)
return false;
divisor++;
}
return true;
}

Неизвестный

12.12.2009, 22:48

общий

это ответ

Здравствуйте, chickencat.
Программа.С++.MS VS 2008.

Код:

#include <iostream>
#include <iomanip>

using namespace std;

typedef unsigned long long _long;

// Проверяет является ли число числом Мерсенна
bool isMersen(_long num)
{
	if(num)
	{
		// Пока не найден нулевой бит
		while(num&1)
		{
			// Сдвигаем вправо
			num>>=1;
		};
		// Если num!=0 то число не является числом Мерсенна
		return !num;
	}
	else
	{
		return false;
	}
}

int main()
{
	_long num;
	cout<<"Enter number:";
	cin>>num;
	cout<<"isMersen("<<num<<")="<<boolalpha<<isMersen(num)<<endl;
	system("PAUSE");
	return 0;
}

Алгоритм основан на том, что требуемое число во всех своих двоичных разрядах содержит единицы. Напр. 2⁸-1=255₁₀=11111111₂
Поэтому производится проверка на отсутствие в числе двоичных нулей.
Примеры работы:

Код:

Enter number:20
isMersen(20)=false

Enter number:254
isMersen(254)=false

Enter number:255
isMersen(255)=true

Enter number:18446744073709551615
isMersen(18446744073709551615)=true

Неизвестный

12.12.2009, 22:49

общий

chickencat:
Ответил.

Неизвестный

12.12.2009, 23:07

общий

leonid59:
Ради интереса проверьте на числе 2⁶⁴-1

Неизвестный

13.12.2009, 09:13

общий

Micren:
И без проверки не будет работать, 2^64 - это 8 байт (при тестировании проверял sizeof(unsigned long long int)=8). Ваша идея со всеми единицами дает на одно число больше по первому варианту, по второму, то есть, с простыми числами, не прибавляется членов. Ваш метод изящней, так как нет дополнительного инкремента (лишней сущности). Это даст больший эффект на длинных числах.

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.