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

Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.77
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
06.03.2012, 18:36     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #1
Найти все простые натуральные числа, не превосходящие n, двоичная
запись которых представляет собой палиндром, т.е. читается одинаково слева направо и справа налево.
Простые натуральные числа это 2,3,5,7 да?
Они должны представляться как 2 системе, т.е.
2 - 0010
3 - 0011
5 - 0101(подходит только это, т.к. читается слева на право одинаковое)
7 - 0111
Я правильно понял?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.03.2012, 18:36     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром
Посмотрите здесь:

a) Найти все натуральные числа, не превосходящие К C++
C++ Циклы.Найти все натуральные числа не превосходящие заданного n, десятичная запись которых есть строго убывающая последовательность цифр
C++ Найти все натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром
C++ Найти все такие простые числа, не превосходящие заданного N, в троичной записи которых цифра 2, встречается заданное число раз
Найти все натуральные числа <= n, десятичная запись которых - строго упорядоченная последовательность C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ZiGSuN
 Аватар для ZiGSuN
27 / 27 / 2
Регистрация: 02.12.2009
Сообщений: 66
06.03.2012, 18:40     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #2
про простые натуральные числа ты понял правильно
а вот палиндром это когда справа-налево читается так же как и слева-направо например 17- 10001
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
06.03.2012, 18:42  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #3
Цитата Сообщение от ZiGSuN Посмотреть сообщение
нет, палиндром это когда справа-налево читается так же как и слева-направо например 17- 10001
А да, но просты натуральные числа это 2,3,5,7 да? в двоичной системе у этих чисел нет такого, чтобы читалось слева на право и наоборот одинаково.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
06.03.2012, 18:44     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #4
Цитата Сообщение от Scaletta Посмотреть сообщение
5 - 0101(подходит только это, т.к. читается слева на право одинаковое)
слева направо — 0101, справа налево — 1010. Где же здесь «одинаково»?

PS. Определение слова «палиндром» можно посмотреть на Википедии.

Добавлено через 43 секунды
Цитата Сообщение от Scaletta Посмотреть сообщение
в двоичной системе у этих чисел нет такого, чтобы читалось слева на право и наоборот одинаково.
а это что тогда?
Цитата Сообщение от ZiGSuN Посмотреть сообщение
а вот палиндром это когда справа-налево читается так же как и слева-направо например 17- 10001
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
06.03.2012, 19:26  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #5
Тогда как мне перести из натуральных чисел в двоичную систему в С++?

Добавлено через 36 минут
Цитата Сообщение от Scaletta Посмотреть сообщение
Тогда как мне перести из натуральных чисел в двоичную систему в С++?
Вот ввести число 55
потом идет цикл
for (i=1;i<=n;i++)
если число натурально=>переводит в 2систему
если нет, ошибка
Как это показать в программе?
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
10.03.2012, 15:52  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #6
Никто не объясни как сделать задачку?
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
10.03.2012, 16:03     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #7
наверно надо считать только значащие цифры, поэтому 0101 == 101 - полиндром
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
10.03.2012, 16:04     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #8
Цитата Сообщение от sandye51 Посмотреть сообщение
наверно надо считать только значащие цифры
я думаю, нужно добавлять и удалять ведущие нули у числа слева от знака сравнения в зависимости от количества значащих разрядов у числа справа от знака сравнения, т.к. 0101 == 1010 — тоже палиндром.
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
10.03.2012, 16:05  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #9
Цитата Сообщение от sandye51 Посмотреть сообщение
наверно надо считать только значащие цифры, поэтому 0101 == 101 - полиндром
Проблема состоит в том, что я могу все это представить, а как написать в программе не знаю, т.к. с этого семестра начали проходить программирование, я себя этим не оправдываю. Как мне избавиться от этой проблемы, знаю, но не пойму как показать в программе?
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
10.03.2012, 16:18     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #10
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
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <cmath>
 
bool is_simple(unsigned int n)
{
    for (unsigned int i = 2, end = static_cast<unsigned int>(pow(static_cast<double>(n), 0.5)); i <= end; ++i)
        if (n % i == 0)
            return false;
    
    return true;
}
 
bool poly(unsigned int n)
{
    unsigned int size = static_cast<unsigned int>(log2(static_cast<double>(n))) + 1;
    char* number = new char[size];
    for (unsigned int i = 0; i < size; ++i)
    {
        number[i] = n & 1 ? '1' : '0';
        n >>= 1;
    }
    
    for (unsigned int i = 0; i < size / 2; ++i)
        if (number[i] != number[size - i - 1])
            return false;
 
    delete[]number;
    return true;
}
 
int main()
{
    unsigned int n;
    
    std::cout << "Введите n: " << std::endl;
    std::cin >> n;
    
    std::cout << "Ответ: " << std::endl;
    for (unsigned int i = 1; i <= n; ++i)
        if (is_simple(i))
            if (poly(i))
                std::cout << i << " ";
    std::cout << std::endl;
    
    system("Pause");
    return EXIT_SUCCESS;
}
сделал так, как имел ввиду выше
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.03.2012, 10:05     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #11
Более оптимальный перебор:
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
#include <iostream>
#include <vector>
#include <cstdio>
 
bool is_poly( unsigned x )
{
    static char bits[32];
    int i = 0;
    
    for ( ; x != 0; x >>= 1)
            bits[i++] = x & 1;
    
    for (int j = 0; j < (i >> 1); ++j)
        if ( bits[j] != bits[i - j - 1] )
            return false;
            
    return true;;
}
 
int main()
{   
    int n;
    
    if ( !(std::cin >> n) )
    {
        std::cerr << "Incorrect input!" << std::endl;
        return 1;
    }
    
    std::vector< bool > sieve( (n >> 1) + 1);
    
    for (int i = 3; i * i <= n; i += 2)
    {
        if ( !sieve[i >> 1] )
        {
            for (int j = (i << 1); j <= n; j += i)
                if ( j & 1 )
                    sieve[j >> 1] = 1;
        }
    }
    
    for (int i = 3; i <= n; i += 2)
    {
        if ( !sieve[i >> 1] && is_poly(i) )
        {
            std::cout << i << ' ';
        }
    }
}
Для n = 10^8 у меня чуть больше секунды работает. Кушает n / 16 байт памяти.
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
12.03.2012, 22:21  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #12
Цитата Сообщение от sandye51 Посмотреть сообщение
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
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <cmath>
 
bool is_simple(unsigned int n)
{
    for (unsigned int i = 2, end = static_cast<unsigned int>(pow(static_cast<double>(n), 0.5)); i <= end; ++i)
        if (n % i == 0)
            return false;
    
    return true;
}
 
bool poly(unsigned int n)
{
    unsigned int size = static_cast<unsigned int>(log2(static_cast<double>(n))) + 1;
    char* number = new char[size];
    for (unsigned int i = 0; i < size; ++i)
    {
        number[i] = n & 1 ? '1' : '0';
        n >>= 1;
    }
    
    for (unsigned int i = 0; i < size / 2; ++i)
        if (number[i] != number[size - i - 1])
            return false;
 
    delete[]number;
    return true;
}
 
int main()
{
    unsigned int n;
    
    std::cout << "Введите n: " << std::endl;
    std::cin >> n;
    
    std::cout << "Ответ: " << std::endl;
    for (unsigned int i = 1; i <= n; ++i)
        if (is_simple(i))
            if (poly(i))
                std::cout << i << " ";
    std::cout << std::endl;
    
    system("Pause");
    return EXIT_SUCCESS;
}
сделал так, как имел ввиду выше
Спасибо огромное...но я тут вообще толком ничего не пойму...

Добавлено через 4 минуты
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
#include<iostream>
using namespace std;
int main()
{
    setlocale(0,"russian");
    system ("color 70");
    
     int n,i,d;
     d=2;
     aa: cout<<"Введите n=";
     cin>>n;
     for (i=2; i<n ; i++)
     {
      if (n%d==0)
      {
          cout<<"Простое число"<<endl;
      }
      else
      {
          cout<<"Ошибка"<<endl;goto aa;
      }
         system ("pause");
      return 0;
}
почему ответ такой выходит http://i31.***********/big/2012/0312/...5ecf0aa3b.jpeg

Добавлено через 3 минуты
C++
1
2
3
4
5
6
for (int i=3; i>=n; i--)
      {
       int bit = ((n >> i) & 1);
       cout << bit;
      }
      cout<<endl;
В интернете нашел как перевести в двоичную систему, как мне состыковать с выше написанной программой?
Не судите строго, хочу разобраться...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.03.2012, 11:03     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром
Еще ссылки по теме:

Найти все простые числа, не превосходящие N, в десятичном представлении которых, нет совпадающих цифр C++
C++ Найти 4-х значные числа, запись которых в hex представляет собой палиндром
Найти простые натуральные числа запись которых представляет собой палиндром C++

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

Или воспользуйтесь поиском по форуму:
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
18.03.2012, 11:03  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #13
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
#include<math.h>
#include<stdio.h>
#include<conio.h>
using namespace std;
 bool simple (int n)
{
         for( int i=2; i<=n/2; i++)
         {
             if(n%2==0) 
                 return 0;
             return 1;
         }
     }
int main()
{
    setlocale(0,"russian");
    system ("color 70");
    cout<<"Работу выполнил ст. гр. И-21"<<endl;
    int n,i,c,B,p,b;
    cout<<"Введите n=";
    cin>>n;
    if (simple(n)) 
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
     for (int i=2; n>0; i++)
     {
         c=n%2;
         n/=2;
         B=B*10+c;
         b=b+c*p;
         p*=10;
 
     }
     system ("pause");
     return 0;
}
Особых продвижений в этом нет, но сдвинулся с мертвой точки.
У меня получилось все таки проверить на простоту число, есть даже перевод в двоичную систему и палиндром, помогите все по полочкам разложить. Спасибо

Добавлено через 3 часа 15 минут
Ну что поможет кто?
Yandex
Объявления
18.03.2012, 11:03     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром
Ответ Создать тему
Опции темы

Текущее время: 09:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru