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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 1
20.09.2013, 22:28     Простые делители числа,задачка! #1
Задача:Простые делители числа 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     Простые делители числа,задачка!
Посмотрите здесь:

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p. C++
C++ Даны целые числа р и q. Получить все делители числа q, взаимно простые с р
Даны целые числа р и q. Получить все делители числа q, взаимно простые с р. C++
Простые делители заданного числа C++
не могу понять задачку :) Даны натуральные числа p и q. Получить все делители числа q, взаимно простые с p C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
castaway
Эксперт С++
4842 / 2981 / 367
Регистрация: 10.11.2010
Сообщений: 11,013
Записей в блоге: 10
Завершенные тесты: 1
20.09.2013, 22:39     Простые делители числа,задачка! #2
А что непонятного? Функция isSimple не всегда может возвратить значение.
egor2116
 Аватар для egor2116
337 / 368 / 42
Регистрация: 20.01.2013
Сообщений: 1,100
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~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 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
 Аватар для fishec
118 / 118 / 30
Регистрация: 07.09.2013
Сообщений: 337
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~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 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
 Аватар для fishec
118 / 118 / 30
Регистрация: 07.09.2013
Сообщений: 337
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~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 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
 Аватар для fishec
118 / 118 / 30
Регистрация: 07.09.2013
Сообщений: 337
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~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 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~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 1
20.09.2013, 23:01  [ТС]     Простые делители числа,задачка! #11
Нет,ошибка.
fishec
 Аватар для fishec
118 / 118 / 30
Регистрация: 07.09.2013
Сообщений: 337
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~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 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
 Аватар для fishec
118 / 118 / 30
Регистрация: 07.09.2013
Сообщений: 337
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~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 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
 Аватар для fishec
118 / 118 / 30
Регистрация: 07.09.2013
Сообщений: 337
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
Эксперт С++
4842 / 2981 / 367
Регистрация: 10.11.2010
Сообщений: 11,013
Записей в блоге: 10
Завершенные тесты: 1
20.09.2013, 23:37     Простые делители числа,задачка! #17
DmitryM5, ты че, деревянный? Я тебе еще во втором посте сказал в чем у тебя проблема. Тебе гордость не позволяет это понять или что?
Если ты вообще ничего не понимаешь, то вот тебе решение:
C++
1
2
if ( flag ) return true;
return false;
Надеюсь догадаешься куда вставить.
Это выражение можно легко заменить на: return !!(flag);
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 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
Эксперт С++
4842 / 2981 / 367
Регистрация: 10.11.2010
Сообщений: 11,013
Записей в блоге: 10
Завершенные тесты: 1
21.09.2013, 00:10     Простые делители числа,задачка! #19
В алгоритм я не вникал, но тут уже нет той проблемы, которую ты обозначил в теме.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.09.2013, 00:37     Простые делители числа,задачка!
Еще ссылки по теме:

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

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

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

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