Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
DmitryM5
Love~
52 / 52 / 23
Регистрация: 27.08.2013
Сообщений: 940
Записей в блоге: 1
#1

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

20.09.2013, 22:28. Просмотров 1438. Ответов 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++):

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

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

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

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

Простые делители заданного числа
Задача из сборника Златопольского 8.54*. Дано натуральное число n. Получить...

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

22
castaway
Эксперт С++
4927 / 3034 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 10
Завершенные тесты: 1
20.09.2013, 22:39 #2
А что непонятного? Функция isSimple не всегда может возвратить значение.
0
egor2116
571 / 375 / 215
Регистрация: 20.01.2013
Сообщений: 1,135
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~
52 / 52 / 23
Регистрация: 27.08.2013
Сообщений: 940
Записей в блоге: 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
121 / 121 / 62
Регистрация: 07.09.2013
Сообщений: 343
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~
52 / 52 / 23
Регистрация: 27.08.2013
Сообщений: 940
Записей в блоге: 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
121 / 121 / 62
Регистрация: 07.09.2013
Сообщений: 343
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~
52 / 52 / 23
Регистрация: 27.08.2013
Сообщений: 940
Записей в блоге: 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
121 / 121 / 62
Регистрация: 07.09.2013
Сообщений: 343
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~
52 / 52 / 23
Регистрация: 27.08.2013
Сообщений: 940
Записей в блоге: 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~
52 / 52 / 23
Регистрация: 27.08.2013
Сообщений: 940
Записей в блоге: 1
20.09.2013, 23:01  [ТС] #11
Нет,ошибка.
0
fishec
121 / 121 / 62
Регистрация: 07.09.2013
Сообщений: 343
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~
52 / 52 / 23
Регистрация: 27.08.2013
Сообщений: 940
Записей в блоге: 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
121 / 121 / 62
Регистрация: 07.09.2013
Сообщений: 343
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~
52 / 52 / 23
Регистрация: 27.08.2013
Сообщений: 940
Записей в блоге: 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
Миниатюры
Простые делители числа,задачка!  
fishec
121 / 121 / 62
Регистрация: 07.09.2013
Сообщений: 343
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;
}
0
castaway
Эксперт С++
4927 / 3034 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 10
Завершенные тесты: 1
20.09.2013, 23:37 #17
DmitryM5, ты че, деревянный? Я тебе еще во втором посте сказал в чем у тебя проблема. Тебе гордость не позволяет это понять или что?
Если ты вообще ничего не понимаешь, то вот тебе решение:
C++
1
2
if ( flag ) return true;
return false;
Надеюсь догадаешься куда вставить.
Это выражение можно легко заменить на: return !!(flag);
0
DmitryM5
Love~
52 / 52 / 23
Регистрация: 27.08.2013
Сообщений: 940
Записей в блоге: 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 не подходит...
0
castaway
Эксперт С++
4927 / 3034 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 10
Завершенные тесты: 1
21.09.2013, 00:10 #19
В алгоритм я не вникал, но тут уже нет той проблемы, которую ты обозначил в теме.
0
fishec
121 / 121 / 62
Регистрация: 07.09.2013
Сообщений: 343
21.09.2013, 00:37 #20
Цитата Сообщение от DmitryM5 Посмотреть сообщение
И этот ответ 600851475143=8462696833*71 не подходит...
Да алгоритм не правильный
0
21.09.2013, 00:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.09.2013, 00:37
Привет! Вот еще темы с решениями:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

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