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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 805
Записей в блоге: 1
#1

Простые делители числа,задачка! - C++

20.09.2013, 22:28. Просмотров 1245. Ответов 22
Метки нет (Все метки)

Задача:Простые делители числа 13195 - это 5, 7, 13 и 29.

Какой самый большой делитель числа 600851475143, являющийся простым числом?

Замечание: число 600851475143 не поместится в тип int, чего не скажешь о типе long long. Этот тип официально включён в стандарт языка C++ лишь с 2011 года, но уже довольно давно доступен в популярных компиляторах языка, в том числе, Visual C++.

Смотреть скрин и помомь

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
#include <iostream>
#include <locale>
 
using namespace std;
 
bool isSimple(long long A) {
    int flag=1;
    for (long long i=2;i<A;i++) {
        if (A%i==0) {
            flag=0;
            return false;
    }
}
    if  (flag=1) return true;
}
 
int main() {
    std::locale::global(std::locale(""));
    long long A=600851475143,result;
 
    for (long long i=2;i<A;i++) {
    if ((A%i==0)&&(isSimple(A))) 
        result=i;
    }
    
    cout<<"Самый большой делитель числа 600851475143,являющийся простым =  "<<result<<endl;
 
system("pause");
return 0;
}
Миниатюры
Простые делители числа,задачка!  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.09.2013, 22:28     Простые делители числа,задачка!
Посмотрите здесь:

Простые делители заданного числа - C++
Задача из сборника Златопольского 8.54*. Дано натуральное число n. Получить все простые делители этого числа #include &lt;iostream&gt; ...

Получить все простые делители числа - C++
Дано натуральное число n. Получить все простые делители этого числа. Помогите пожалуйста.

Получить все простые делители числа - C++
Здравствуйте, помогите, пожалуйста. Дано целое число n. Получить все простые делители этого числа.

Вывести все простые делители числа - C++
Люди помогите с лабами до субботы надо сдать!!! 1. Ввести целое число N. Вывести все простые делители этого числа. 2. Ввести строку...

Получить все простые делители заданного числа - C++
Дано натуральное число n. Получить все простые делители этого числа. (нужно использовать функцию) #include &lt;iostream&gt; #include...

Получить все простые делители натурального числа - C++
2. Дано натуральное число n. Получить все простые делители этого числа.

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 10
Завершенные тесты: 1
20.09.2013, 22:39     Простые делители числа,задачка! #2
А что непонятного? Функция isSimple не всегда может возвратить значение.
egor2116
339 / 370 / 42
Регистрация: 20.01.2013
Сообщений: 1,123
20.09.2013, 22:41     Простые делители числа,задачка! #3
C++
1
2
3
4
5
6
7
8
9
10
11
bool isSimple(long long A) {
    int flag=1;
    for (long long i=2;i<A;i++) {
        if (A%i==0) {
            flag=0;
            return false;
    }
     //ВОТ ТУТ ДОЛЖЕН БЫТЬ ЕЩЕ 1 RETURN
}
    if  (flag=1) return true;
}
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 805
Записей в блоге: 1
20.09.2013, 22:44  [ТС]     Простые делители числа,задачка! #4
Цитата Сообщение от egor2116 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
bool isSimple(long long A) {
    int flag=1;
    for (long long i=2;i<A;i++) {
        if (A%i==0) {
            flag=0;
            return false;
    }
     //ВОТ ТУТ ДОЛЖЕН БЫТЬ ЕЩЕ 1 RETURN
}
    if  (flag=1) return true;
}
Может я что-то не понимаю,но ты о чем?
Быть может мне еще туда 5 штук return сделать?Тем более ты мне его в if предлагаешь сделать,где он уже есть...
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
20.09.2013, 22:48     Простые делители числа,задачка! #5
Цитата Сообщение от DmitryM5 Посмотреть сообщение
if (flag=1) return true;
== мб?

Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
bool isSimple(long long A) {
     for (long long i=2;i<A/2+1;i++) {
        if (A%i==0) {
            return false;
        }
     }
return true;
}
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 805
Записей в блоге: 1
20.09.2013, 22:49  [ТС]     Простые делители числа,задачка! #6
Цитата Сообщение от fishec Посмотреть сообщение
== мб?

Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
bool isSimple(long long A) {
     for (long long i=2;i<A/2+1;i++) {
        if (A%i==0) {
            return false;
        }
     }
return true;
}
Да это ошибка,но справив её тоже самое...
Вот без флага код,он там вообще не нужен.
C++
1
2
3
4
5
6
7
8
bool isSimple(long long A) {
    for (long long i=2;i<A;i++) {
        if (A%i==0)
            return false;
   
}
   return true;
}
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
20.09.2013, 22:51     Простые делители числа,задачка! #7
Вообще достаточно от 2 до sqrt(A) искать делители.

Добавлено через 1 минуту
C++
1
2
3
4
5
6
for (long long i=A ;i>1 ;i--) {
    if ((A%i==0)&&(isSimple(A)))
        result=i;
        break;
    }
}
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 805
Записей в блоге: 1
20.09.2013, 22:51  [ТС]     Простые делители числа,задачка! #8
Цитата Сообщение от fishec Посмотреть сообщение
Вообще достаточно от 2 до sqrt(A) искать делители.

Добавлено через 1 минуту
C++
1
2
3
4
5
6
for (long long i=A ;i>1 ;i--) {
    if ((A%i==0)&&(isSimple(A)))
        result=i;
        break;
    }
}
Если число составное, то есть представляет собой произведение простых сомножителей, то среди этих сомножителей обязательно должен найтись хотя бы один, который будет меньше квадратного корня из заданного числа. Ведь произведение двух чисел, каждое из которых больше квадратного корня из некоторого X, будет заведомо больше X, и эти два числа никак не могут быть его делителями.

А если данное число не составное?


Черный экран теперь просто.
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
20.09.2013, 22:55     Простые делители числа,задачка! #9
Цитата Сообщение от DmitryM5 Посмотреть сообщение
А если данное число не составное?
тогда оно простое, и результат функции true

Добавлено через 1 минуту
C++
1
2
3
4
5
6
for (long long i=A ;i>1 ;i--) {
    if (isSimple(i)&&(A%i==0))
        result=i;
        break;
    }
}
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 805
Записей в блоге: 1
20.09.2013, 22:58  [ТС]     Простые делители числа,задачка! #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
#include <iostream>
#include <locale>
#include <math.h>
 
using namespace std;
 
bool isSimple(long long A) {
    for (long long i=2;i<sqrt(A);i++) {
        if (A%i==0)
            return false;
   
}
   return true;
}
 
 
int main() {
    std::locale::global(std::locale(""));
    long long A=600851475143,result=-1;
 
    for (long long i=A;i>1;i--) {
    if ((A%i==0)&&(isSimple(A))) 
        result=i;
        break;
    }
    
    cout<<"Самый большой делитель числа 600851475143,являющийся простым =  "<<result<<endl;
 
system("pause");
return 0;
}
Из скрина выходит,что это огромное число и есть простое?
Миниатюры
Простые делители числа,задачка!  
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 805
Записей в блоге: 1
20.09.2013, 23:01  [ТС]     Простые делители числа,задачка! #11
Нет,ошибка.
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
20.09.2013, 23:06     Простые делители числа,задачка! #12
Цитата Сообщение от DmitryM5 Посмотреть сообщение
for (long long i=A;i>1;i--) { if ((A%i==0)&&(isSimple(A))) result=i; break;
тут ошибка isSimple должно быть от i

Добавлено через 3 минуты
600851475143=8462696833*71
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 805
Записей в блоге: 1
20.09.2013, 23:06  [ТС]     Простые делители числа,задачка! #13
Цитата Сообщение от fishec Посмотреть сообщение
тут ошибка isSimple должно быть от i
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
#include <iostream>
#include <locale>
#include <math.h>
 
using namespace std;
 
bool isSimple(long long A) {
    for (long long i=2;i<sqrt(A);i++) {
        if (A%i==0)
            return false;
   
}
   return true;
}
 
 
int main() {
    std::locale::global(std::locale(""));
    long long A=600851475143,result=-1;
 
    for (long long i=A;i>1;i--) {
    if ((A%i==0)&&(isSimple(i))) 
        result=i;
        break;
    }
    
    cout<<"Самый большой делитель числа 600851475143,являющийся простым =  "<<result<<endl;
 
system("pause");
return 0;
}
Блин что опять не так!?
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
20.09.2013, 23:09     Простые делители числа,задачка! #14
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
long long A=600851475143,result=1;
for (long long i=2 ;i<=sqrt(A) ;i++) {
    if (isSimple(i)&&(A%i==0)){
        result=i;
        break;
    }
}
result=A/result;
cout<<result<<endl;
 
system("pause");
return 0;
}
Добавлено через 2 минуты
С конца долго ищет. Нужно с начала. Найдет быстро число 71. И потом делишь A на 71 и получаешь результат
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 805
Записей в блоге: 1
20.09.2013, 23:19  [ТС]     Простые делители числа,задачка! #15
Цитата Сообщение от fishec Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
long long A=600851475143,result=1;
for (long long i=2 ;i<=sqrt(A) ;i++) {
    if (isSimple(i)&&(A%i==0)){
        result=i;
        break;
    }
}
result=A/result;
cout<<result<<endl;
 
system("pause");
return 0;
}
Добавлено через 2 минуты
С конца долго ищет. Нужно с начала. Найдет быстро число 71. И потом делишь A на 71 и получаешь результат

C++
1
2
3
4
5
6
7
8
9
long long A=600851475143,result=1;
 
    for (long long i=2;i<=sqrt(A);i++) {
    if ((isSimple(i))&&(A%i==0)) 
        result=i;
        break;
    }
    result=A/result;
    cout<<"Самый большой делитель числа 600851475143,являющийся простым =  "<<result<<endl;
Кхм...
Миниатюры
Простые делители числа,задачка!  
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
20.09.2013, 23:31     Простые делители числа,задачка! #16
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 <vcl.h>
#include <iostream>
#include <math.h>
using namespace std;
 
bool isSimple(long long A) {
    for (long long i=2;i<=sqrt(A);i++) {
        if (A%i==0){
            return false;
        }
    }
    return true;
}
int main(){
long long A=600851475143,result=1;
for (long long i=2 ;i<=sqrt(A) ;i++) {
    if (isSimple(i)&&(A%i==0)){
        result=i;
        break;
    }
}
result=A/result;
cout<<result<<endl;
system("pause");
return 0;
}
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 10
Завершенные тесты: 1
20.09.2013, 23:37     Простые делители числа,задачка! #17
DmitryM5, ты че, деревянный? Я тебе еще во втором посте сказал в чем у тебя проблема. Тебе гордость не позволяет это понять или что?
Если ты вообще ничего не понимаешь, то вот тебе решение:
C++
1
2
if ( flag ) return true;
return false;
Надеюсь догадаешься куда вставить.
Это выражение можно легко заменить на: return !!(flag);
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 805
Записей в блоге: 1
21.09.2013, 00:00  [ТС]     Простые делители числа,задачка! #18
Цитата Сообщение от castaway Посмотреть сообщение
DmitryM5, ты че, деревянный? Я тебе еще во втором посте сказал в чем у тебя проблема. Тебе гордость не позволяет это понять или что?
Если ты вообще ничего не понимаешь, то вот тебе решение:
C++
1
2
if ( flag ) return true;
return false;
Надеюсь догадаешься куда вставить.
Это выражение можно легко заменить на: return !!(flag);
Оловянный я.
Уже без флагов сделали,что тут не так тоже чтоли??
C++
1
2
3
4
5
6
7
8
bool isSimple(long long A) {
    for (long long i=2;i<sqrt(A);i++) {
        if (A%i==0)
            return false;
   
}
   return true;
}


И этот ответ 600851475143=8462696833*71 не подходит...
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 10
Завершенные тесты: 1
21.09.2013, 00:10     Простые делители числа,задачка! #19
В алгоритм я не вникал, но тут уже нет той проблемы, которую ты обозначил в теме.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.09.2013, 00:37     Простые делители числа,задачка!
Еще ссылки по теме:

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

Получить все простые делители заданного натурального числа - C++
Бьюсь с этой задачей уже несколько часов. Выдает сбой в вычислениях, и я не могу понять почему. За проверку брал число 1463....

Найти все простые положительные делители данного натурального числа - C++
Help!: Дано натуральное число N. Найти все его простые положительные делители. Ещё с решением пожалуйста (алгоритмы)

Дано целое число n. Получить все простые делители этого числа - C++
Почему простые делители выдает не правильно? ch-число del-делитель dd-делитель делителя #include &quot;stdafx.h&quot; #include...

Ввести целое число N. Вывести все простые делители этого числа - C++
прошу помочь над 2 задачами в с++: 1. Ввести целое число N. Вывести все простые делители этого числа 2. Ввести строку и слово,...


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

Или воспользуйтесь поиском по форуму:
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
21.09.2013, 00:37     Простые делители числа,задачка! #20
Цитата Сообщение от DmitryM5 Посмотреть сообщение
И этот ответ 600851475143=8462696833*71 не подходит...
Да алгоритм не правильный
Yandex
Объявления
21.09.2013, 00:37     Простые делители числа,задачка!
Ответ Создать тему
Опции темы

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