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

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

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

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

20.09.2013, 22:28. Просмотров 1296. Ответов 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;
}
0
Миниатюры
Простые делители числа,задачка!  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.09.2013, 22:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Простые делители числа,задачка! (C++):

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

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

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

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

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

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

22
castaway
Эксперт С++
4884 / 3019 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
20.09.2013, 22:39 #2
А что непонятного? Функция isSimple не всегда может возвратить значение.
0
egor2116
339 / 370 / 42
Регистрация: 20.01.2013
Сообщений: 1,126
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;
}
0
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 840
Записей в блоге: 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 предлагаешь сделать,где он уже есть...
0
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;
}
1
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 840
Записей в блоге: 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;
}
0
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;
    }
}
1
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 840
Записей в блоге: 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, и эти два числа никак не могут быть его делителями.

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


Черный экран теперь просто.
0
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;
    }
}
1
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 840
Записей в блоге: 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;
}
Из скрина выходит,что это огромное число и есть простое?
0
Миниатюры
Простые делители числа,задачка!  
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 840
Записей в блоге: 1
20.09.2013, 23:01  [ТС] #11
Нет,ошибка.
0
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
1
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 840
Записей в блоге: 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;
}
Блин что опять не так!?
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 и получаешь результат
0
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 840
Записей в блоге: 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;
Кхм...
0
Миниатюры
Простые делители числа,задачка!  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.09.2013, 23:19
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
20.09.2013, 23:19
Ответ Создать тему
Опции темы

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