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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.93
MoNoMiZe
0 / 0 / 0
Регистрация: 20.09.2010
Сообщений: 8
25.09.2010, 16:35     Простые числа #1
Доброго времени суток!

Необходима Ваша помощь в написании программы на visual c++. Программы должна выводить все простые числа из заданного промежутка (начало и конец вводятся с клавиатуры) в виде
1 3 5 7
11 13 17 19
и так далее.

Заранее спасибо!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Rajd
 Аватар для Rajd
44 / 22 / 1
Регистрация: 20.11.2008
Сообщений: 178
25.09.2010, 17:08     Простые числа #2
тебе что нужно код за тебя написать или подсобить с алгоритмом, а с кодом ты будешь сам изголяться, свои мозхги подключались к ентому вопросу?
Ни в коем случае не сочтите за оскорбление, просто случаи бывают всякие.
 Комментарий модератора 
Отправка во фриланс запрещена в тематических разделах
MoNoMiZe
0 / 0 / 0
Регистрация: 20.09.2010
Сообщений: 8
25.09.2010, 17:14  [ТС]     Простые числа #3
код конечно тоже не помешает, больше всего интересует часть кода с определением числа на простоту. желательно с комментами)
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
25.09.2010, 17:17     Простые числа #4
1. 1..N
самый простой вариант
C++
1
2
3
4
5
6
7
8
9
10
for( int i=1;i<N;++i ){
  for( int j=1;j<i;++j ){
    if( i % j == 0 ){
      break;
    }
  }
  if( i == j ){
    cout << i << endl;
  }
}
2. с проблеском мысли
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 100;
 
int main(){
  int nArr[N];
  for( int i=1;i<N;++i ){
    nArr[i] = i;
  }
  for( int i=2;i<N;++i ){
    for( int j=2;j<=i && i*j<N;++j ){
       if( 0 != nArr[j] ){ nArr[j*i] = 0; } 
    }
  }
  for( int i=1;i<N;++i ){
    if( nArr[i] != 0 ) cout << i << endl;
  }
}
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
25.09.2010, 17:20     Простые числа #5
Цитата Сообщение от MoNoMiZe Посмотреть сообщение
больше всего интересует часть кода с определением числа на простоту
Перебором делителей:
C++
1
2
3
4
5
6
7
8
9
10
11
// Проверяет является ли число n простым
bool IsSimple(int n) {
  if (n < 2)
    return false;
 
  for (int j = 2; j * j <= n; ++j)
    if (n % j == 0) 
      return false;
 
  return true;
}
Rajd
 Аватар для Rajd
44 / 22 / 1
Регистрация: 20.11.2008
Сообщений: 178
25.09.2010, 17:30     Простые числа #6
Алгоритм определения простого числа прост, обычно (сколько учебных пособий я пролистал в своих поисках нужных мне ответов) такое пишут почти в самом начале учебника

принцип прост это цикл который проверяет делимость нужного нам числа на числа от 2 до половины данного числа с ппомощью оператора "%"

Добавлено через 4 минуты
CyBOSSeR, аозьму за основу твой код. не сочти за плагиат.
C++
1
2
3
4
5
6
7
bool IsSimple(int x) {
int k;
for(k=2;k<=(x<<1);k++){
?(x%k==0):return false;
}
  return true;
}
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
25.09.2010, 17:32     Простые числа #7
Цитата Сообщение от Rajd Посмотреть сообщение
?(x%k==0):return false;
Что это?
MoNoMiZe
0 / 0 / 0
Регистрация: 20.09.2010
Сообщений: 8
25.09.2010, 17:36  [ТС]     Простые числа #8
всем большое спасибо)

а как еще осуществить вывод на экран простых чисел по десяткам? все просты от 0 до 10 - в 1 строке, от 11 до 20 - во второй и так далее
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
25.09.2010, 17:41     Простые числа #9
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Перебором делителей:
C++
1
2
3
4
...
  if (n < 2)
    return false;
...
А 1 разве простым числом не считается? Может как-то так?
C++
1
2
3
4
...
if ( n < 2 )
  return ( n == 1 );
...
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
25.09.2010, 17:44     Простые числа #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
#include <iostream>
#include <ctime>
#include <cmath>
 
using namespace std;
 
const int N = 100;
 
int main(){
    int nArr[N], nLast = 1;
    for( int i=1;i<N;++i ){
        nArr[i] = i;
    }
    for( int i=2;i<N;++i ){
        if( 0 == nArr[i] ) continue; 
        for( int j=2;j<N && i*j<N;++j ){
            nArr[j*i] = 0;
        }
    }
    for( int i=1;i<N;++i ){
        if( nArr[i] != 0 ){
            if( i >= nLast*10 ){ nLast = i / 10 + 1; cout << endl; }
            cout << i << " ";
        }
    }
}
MoNoMiZe
0 / 0 / 0
Регистрация: 20.09.2010
Сообщений: 8
25.09.2010, 17:45  [ТС]     Простые числа #11
Цитата Сообщение от easybudda Посмотреть сообщение
А 1 разве простым числом не считается? Может как-то так?
C++
1
2
3
4
...
if ( n < 2 )
  return ( n == 1 );
...
я сделал
C++
1
2
if (n < 1)
    return false;
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
25.09.2010, 17:45     Простые числа #12
Цитата Сообщение от easybudda Посмотреть сообщение
А 1 разве простым числом не считается?
Фиг его знает, но Википедия утверждает, что нет.
Rajd
 Аватар для Rajd
44 / 22 / 1
Регистрация: 20.11.2008
Сообщений: 178
25.09.2010, 17:50     Простые числа #13
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Что это?
условный оператор. если мне память не отшибло проверяем остаток от деления.

Добавлено через 43 секунды
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Фиг его знает, но Википедия утверждает, что нет.
действительно нет, просто не подходит под определение в виду того что имеет всего один делитель.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
25.09.2010, 17:52     Простые числа #14
Просто́е число́ — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя
ну наверное так...
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
25.09.2010, 18:03     Простые числа #15
Цитата Сообщение от Rajd Посмотреть сообщение
условный оператор. если мне память не отшибло проверяем остаток от деления.
Это очень похоже на безусловный тернарный оператор.
Оно вообще работает? Если даже да - никогда так не делайте - можно и без рук остаться.
if то Вам, кстати, чем не угодил?
Rajd
 Аватар для Rajd
44 / 22 / 1
Регистрация: 20.11.2008
Сообщений: 178
25.09.2010, 18:19     Простые числа #16
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Это очень похоже на безусловный тернарный оператор.
Оно вообще работает? Если даже да - никогда так не делайте - можно и без рук остаться.

о, точно не правильно написал сори за ошибку.
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
if то Вам, кстати, чем не угодил?
он длинный для этого кода.
MoNoMiZe
0 / 0 / 0
Регистрация: 20.09.2010
Сообщений: 8
25.09.2010, 18:42  [ТС]     Простые числа #17
не могли бы подправить код
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
bool IsSimple(int n) 
{
    if(n<1)
    return false; 
    for(int j = 2; j * j <= n; ++j)
        if (n % j == 0) 
        {
            return false;
        }
        return true;
}
 
int main()
{
        setlocale(0,"");
        int a, b, k = 1;
        cout<<"Введите начало промежутка: ";
        cin>>a;
        cout<<"Введите конец промежутка: ";
        cin>>b;
        for(int i = a; i <= b; i++)
        { 
            if(IsSimple(i))
            {
                if( i > k*10)
                cout << endl;
                cout << i << " ";
            }
        }
        getch();
        return 0;
}
куда именно надо вставить цикл по K, что бы все выводилось так как нужно?
Rajd
 Аватар для Rajd
44 / 22 / 1
Регистрация: 20.11.2008
Сообщений: 178
26.09.2010, 05:56     Простые числа #18
Цитата Сообщение от MoNoMiZe Посмотреть сообщение
куда именно надо вставить цикл по K, что бы все выводилось так как нужно?
Что за цикл по k? и для чего он тебе нужен?

Добавлено через 5 минут
ВО переделал свой код функции. жаль что сообщение свое подправить не могу, там ОШИБИЩА спс
CyBOSSeR, что помог.

C++
1
2
3
4
5
6
7
bool IsSimple(int x) {
int k=2;
while(k<=(x<<1)){
(x%k==0)?return false:k++;
}
  return true;
}
MoNoMiZe
0 / 0 / 0
Регистрация: 20.09.2010
Сообщений: 8
26.09.2010, 13:09  [ТС]     Простые числа #19
уже разобрался, всем еще раз спасибо, тема закрыта)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.05.2012, 15:36     Простые числа
Еще ссылки по теме:

Найти все простые числа от 1000 до 1999, в каждом из которых сумма первой и второй цифр в записи этого числа равна сумме третьей и четвертой. C++
Числа Фибоначчи, простые числа и делители C++
C++ Вывести все простые числа до заданного числа

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

Или воспользуйтесь поиском по форуму:
Dghek
0 / 0 / 0
Регистрация: 26.04.2012
Сообщений: 3
07.05.2012, 15:36     Простые числа #20
А кто нибудь знает алгоритм поиска простых чисел, чтобы он не жрал много памяти...
Ведь, к примеру, используя решето Эратосфена, на определения числа порядка 1 млн тратится около 1 Мб, а на число порядка 1 млрд 1 Гб и т.д.
Если такой алгоритм есть - подскажите.
Yandex
Объявления
07.05.2012, 15:36     Простые числа
Ответ Создать тему
Опции темы

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