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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
KpoccoB0K
1 / 1 / 0
Регистрация: 08.02.2010
Сообщений: 22
#1

Найти на промежутке от 1 до N все числа, взаимно простые с N - C++

03.06.2010, 11:47. Просмотров 1117. Ответов 17
Метки нет (Все метки)

Ребят, помогите пожалуйста с простыми числами.

задача: дайтся число от 1(n). найти в промежутке между 1 и n все простые числа с n.
То есть надо найти те числа, у которых с n самый большой делитель =1.
3 дня не могу добится результата, завтра сдавать, спасите!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2010, 11:47     Найти на промежутке от 1 до N все числа, взаимно простые с N
Посмотрите здесь:

Найти все натуральные числа меньше n и взаимно простые с ним - C++
Прошу помочь написать программу на с++. Само здание: Дано натуральное число n. Получить все натуральные числа меньше n и взаимно простые с...

Получить все делители числа q, взаимно простые с р - C++
3.Даны натуральные числа р и q. Получить все делители числа q, взаимно простые с р заранее спасибо

Получить все делители числа q, взаимно простые к p - C++
Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p. помогите пожалуйста.

выписать все натуральные числа,взаимно простые с m, из отрезка [1;m-1] - C++
выписать все натуральные числа,взаимно простые с m, из отрезка

Получить все натуральные числа, меньшие n и взаимно простые с p - C++
Помогите сделать программу! Даны целые числа n и m. Получить все натуральные числа, меньшие n и взаимно простые с p! Заранее спасибо!

Получить все натуральные числа, меньше n и взаимно простые с ним - C++
Дано натуральное число n. Получить все натуральные числа, меньше n и взаимно простые с ним.

Цикл с while: найти простые числа в промежутке [a, b] - C++
Помогите задачу сделать, кому не трудно. "Напишите программу нахождения простых чисел в промежутке . Напишите программу нахождения на...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
neske
1473 / 840 / 73
Регистрация: 26.03.2010
Сообщений: 2,882
03.06.2010, 12:00     Найти на промежутке от 1 до N все числа, взаимно простые с N #2
Так?
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>
bool func (int, int);
 
int main()
{
    int val;
    std::cout << "Input number: ";
    std::cin >> val;
 
    std::cout << "Found: ";
    for (int i=1; i<=val; i++)
        if (func (val, i)) std::cout << i << " ";
 
    std::cout << std::endl;
    system ("pause");
    return 0;
}
 
bool func (int val, int i)
{
    for (int j=2; j<val; j++)
        if (!(val%j) && !(i%j)) return false;
    return true;
}
KpoccoB0K
1 / 1 / 0
Регистрация: 08.02.2010
Сообщений: 22
03.06.2010, 12:21  [ТС]     Найти на промежутке от 1 до N все числа, взаимно простые с N #3
да не особо так... надо ВЫВЕСТИ те числа у которых с данным числом максимальный ОБЩИЙ делитель равен 1.

то что у Вас написано, выдаёт результат
"21"
что ни к селу ни к городу.

к примеру если задано число "20", то на экран выводятся числа:
3 7 9 11 13 17 19
neske
1473 / 840 / 73
Регистрация: 26.03.2010
Сообщений: 2,882
03.06.2010, 12:24     Найти на промежутке от 1 до N все числа, взаимно простые с N #4
к примеру если задано число "20", то на экран выводятся числа:
3 7 9 11 13 17 19
А какие еще общие делители есть?
KpoccoB0K
1 / 1 / 0
Регистрация: 08.02.2010
Сообщений: 22
03.06.2010, 12:26  [ТС]     Найти на промежутке от 1 до N все числа, взаимно простые с N #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream.h>
#include <conio.h>
int i,n;
main(){
    cout<<"n="; cin>>n;
    for (i=1;i<=n;i++)
        if(n%i!=0)
            if((i%2!=0)&&(n%2!=0))
            if((i%3!=0)&&(n%3!=0))
            if((i%5!=0)&&(n%5!=0))
                        if((i%7!=0)&&(n%7!=0))
                cout<<i<<" ";
getch();
}


думаю суть понятна... но проблема в том что когда в if ставлю "&&" то оно мне вообще ничего не выводит... хотя насколько я знаю, должно вывести те числа которые соответсвуют критериям отбора

Добавлено через 39 секунд
Цитата Сообщение от neske Посмотреть сообщение
А какие еще общие делители есть?
не понял вопроса?... общий делительно только один, и он равен 1 !
neske
1473 / 840 / 73
Регистрация: 26.03.2010
Сообщений: 2,882
03.06.2010, 12:28     Найти на промежутке от 1 до N все числа, взаимно простые с N #6
Вы вводите число 20.
Нужно найти все числа на промежутке 1..20, у которых с числом 20 будет максимальный общий делитель единица.

к примеру если задано число "20", то на экран выводятся числа:
3 7 9 11 13 17 19
Вы говорите неверно.
Я вас и спрашиваю, в таком случае назовите мне еще общие делители для пар (3,20), (7,20) и т.п., не считая единицу?
Жду.
KpoccoB0K
1 / 1 / 0
Регистрация: 08.02.2010
Сообщений: 22
03.06.2010, 12:43  [ТС]     Найти на промежутке от 1 до N все числа, взаимно простые с N #7
общих больше нету вроде(упор делаю на свои математические знания).
3 и 20, 7 и 20. кроме 1 больше ничего нету.
neske
1473 / 840 / 73
Регистрация: 26.03.2010
Сообщений: 2,882
03.06.2010, 12:44     Найти на промежутке от 1 до N все числа, взаимно простые с N #8
А что вы мне тогда говорите?
Программа работает правильно.

3 7 9 11 13 17 19, с каждым из них с числом 20 будет один общий делитель, единица.
KpoccoB0K
1 / 1 / 0
Регистрация: 08.02.2010
Сообщений: 22
03.06.2010, 12:46  [ТС]     Найти на промежутке от 1 до N все числа, взаимно простые с N #9
Ваша программа выдала мне результат: 21.

при чём тут вообще 21? что оно означает? я этого не могу понять.
neske
1473 / 840 / 73
Регистрация: 26.03.2010
Сообщений: 2,882
03.06.2010, 12:49     Найти на промежутке от 1 до N все числа, взаимно простые с N #10
KpoccoB0K, Какое число вы ввели?

Что все не так?
Миниатюры
Найти на промежутке от 1 до N все числа, взаимно простые с N  
neske
1473 / 840 / 73
Регистрация: 26.03.2010
Сообщений: 2,882
03.06.2010, 12:53     Найти на промежутке от 1 до N все числа, взаимно простые с N #11
Тут еще кнопка есть, сказать спасибо.
KpoccoB0K
1 / 1 / 0
Регистрация: 08.02.2010
Сообщений: 22
03.06.2010, 12:54  [ТС]     Найти на промежутке от 1 до N все числа, взаимно простые с N #12
может проблема в том что я немного изменил ваш код из-за того что у нас скорее всего компиляторы не соответсвуют... может из-за этого и результат другой.


тогда будет небольшая просьба.. я сейчас в колледже сижу, поэтому компилятор стандартный(Turbo C++).

если Вам не сложно, то оптимизируйте её под стандартный компилятор, потому что я много чего не понял из того кода....
neske
1473 / 840 / 73
Регистрация: 26.03.2010
Сообщений: 2,882
03.06.2010, 12:58     Найти на промежутке от 1 до N все числа, взаимно простые с 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
#include <iostream>
bool func (int, int); // прототип к функции.
 
int main()
{
    int val;
    std::cout << "Input number: ";
    std::cin >> val; // вводим число.
 
    std::cout << "Found: ";
    for (int i=1; i<=val; i++)
        if (func (val, i)) std::cout << i << " "; // если функция возвратила значениу true - выводим i на экран.
 
    std::cout << std::endl;
    system ("pause");
    return 0;
}
 
bool func (int val, int i)
{
    for (int j=2; j<val; j++)
        if (!(val%j) && !(i%j)) return false;
    // аналогично: if ((val%j==0) && (i%j==0)) return false;
    // то есть, если мы нашли общий делитель, отличный от единицы, то возвращаем false.
    // если мы прошли циклом до конца, но такого не нашли, возвращаем true.
    return true;
}

Посмотрите, я думаю понятней будет.
в Turbo C++ по идее должно работать, но всякое бывает.
KpoccoB0K
1 / 1 / 0
Регистрация: 08.02.2010
Сообщений: 22
03.06.2010, 13:06  [ТС]     Найти на промежутке от 1 до N все числа, взаимно простые с N #14
в Turbo C++ выдаёт ошибку на bool func (int val, int i)
а после if (!(val%j) && !(i%j)) вообще ничего не выдаёт.

Добавлено через 43 секунды
то есть у меня почему-то двойное условие для if не работает((( *бъется об стенку*

Добавлено через 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
#include <iostream.h>
#include <conio.h>
int val,i;
int func(int, int)
{
    for (int j=2; j<val; j++)
    if ((val%j!=0)&&(i%j!=0))
    return 0;
    else
    return 1;
}
 
 
int main()
{
clrscr();
    cout << "Input number: ";
    cin >> val;
 
    cout << "Found: ";
    for (int i=1; i<=val; i++)
    if (func (val, i)) cout << i << " ";
 
    cout << endl;
getch();
}
после этого кода от мне тупо выдает числа от 1 до 20.
neske
1473 / 840 / 73
Регистрация: 26.03.2010
Сообщений: 2,882
03.06.2010, 13:08     Найти на промежутке от 1 до N все числа, взаимно простые с N #15
СТрочка #7 неверно, так должно быть:
C++
1
if ((val%j==0)&&(i%j==0))
KpoccoB0K
1 / 1 / 0
Регистрация: 08.02.2010
Сообщений: 22
03.06.2010, 13:14  [ТС]     Найти на промежутке от 1 до N все числа, взаимно простые с N #16
уже полностью молчит. считывает число и всё.

Добавлено через 1 минуту
о всё!)))

Добавлено через 3 минуты
но одна проблема, проверьте тоже... при вводе числа заканчивающиеся на 5, выдаются числа от 1 до *5.
neske
1473 / 840 / 73
Регистрация: 26.03.2010
Сообщений: 2,882
03.06.2010, 13:29     Найти на промежутке от 1 до N все числа, взаимно простые с N #17
KpoccoB0K, спасибо.
Нашел я ошибку.
Исправленный вариант:
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
#include <iostream>
bool func (int, int); // прототип к функции.
 
int main()
{
    int val;
    std::cout << "Input number: ";
    std::cin >> val; // вводим число.
 
    std::cout << "Found: ";
    for (int i=2; i<=val; i++)
        if (func (val, i)) std::cout << i << " "; // если функция возвратила значениу true - выводим i на экран.
 
    std::cout << std::endl;
    system ("pause");
    return 0;
}
 
bool func (int val, int i)
{
    for (int j=2; j<=i; j++)
        if (!(val%j) && !(i%j)) return false;
    // аналогично: if ((val%j==0) && (i%j==0)) return false;
    // то есть, если мы нашли общий делитель, отличный от единицы, то возвращаем false.
    // если мы прошли циклом до конца, но такого не нашли, возвращаем true.
    return true;
}
Миниатюры
Найти на промежутке от 1 до N все числа, взаимно простые с N  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.06.2010, 14:20     Найти на промежутке от 1 до N все числа, взаимно простые с N
Еще ссылки по теме:

Дано натуральное число k. Получите все натуральные числа, меньшие k и взаимно простые с ним - C++
Тест. k=24. Результат. 1; 5; 7; 11; 13; 17, 19; 23. Помогите с написанием программы, желательно с комментариями..заранее спасибо.

Дано натуральное число n. Вывести на экран все натуральные числа, меньше n и взаимно простые с ним. - C++
Помогите пожалуйста, мне на завтра 2 проги в универ, а я совсем не знаю как их сделать((( 1)Дано натуральное n(n&lt;100), целые числа...

Взаимно простые числа - C++
Два натуральных числа a и b называются взаимно простыми, если их наибольший общий делитель равен 1. Несколько натуральных чисел называются...

Взаимно простые числа - C++
Задание таково:составить программу, отвечающую на вопрос, являются ли два произвольных натуральных числа взаимно простыми. на С++

Взаимно простые числа - C++
Задание таково:составить программу, отвечающую на вопрос, являются ли два произвольных натуральных числа взаимно простыми. З.Ы. Я...


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

Или воспользуйтесь поиском по форуму:
KpoccoB0K
1 / 1 / 0
Регистрация: 08.02.2010
Сообщений: 22
03.06.2010, 14:20  [ТС]     Найти на промежутке от 1 до N все числа, взаимно простые с N #18
Оптимизированный вариант под базовые компиляторы(может кому-то еще пригодится)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream.h>
#include <conio.h>
int i,val,j;
int func(int, int)
{
    for (j=2; j<=i; j++)
        if (!(val%j)&&!(i%j))
 return 0;
 return 1;
} 
int main()
{
    cout<<"Input number: ";
    cin>>val;
    cout<<"Found: ";
    for (i=2; i<=val; i++)
        if (func (val, i)) cout<<i<<" "; 
   cout<<endl;
    getch();
}


neske, Огромнейшее Вам спасибо.
Yandex
Объявления
03.06.2010, 14:20     Найти на промежутке от 1 до N все числа, взаимно простые с N
Ответ Создать тему
Опции темы

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