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

@DmitryM5 · Регистрация: 27.08.2013

Author24 — интернет-сервис помощи студентам

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

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

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

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

C++

#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;
}

@castaway · 20.09.2013, 22:39

А что непонятного? Функция isSimple не всегда может возвратить значение.

@egor2116 · 20.09.2013, 22:41

C++

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 · 20.09.2013, 22:44 **[ТС]**

Сообщение от egor2116

C++

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 · 20.09.2013, 22:48

Сообщение от DmitryM5

if (flag=1) return true;

== мб?

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

C++

bool isSimple(long long A) {
     for (long long i=2;i<A/2+1;i++) {
        if (A%i==0) {
            return false;
        }
     }
return true;
}

@DmitryM5 · 20.09.2013, 22:49 **[ТС]**

Сообщение от fishec

== мб?

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

C++

bool isSimple(long long A) {
     for (long long i=2;i<A/2+1;i++) {
        if (A%i==0) {
            return false;
        }
     }
return true;
}

Да это ошибка,но справив её тоже самое...
Вот без флага код,он там вообще не нужен.

C++

bool isSimple(long long A) {
    for (long long i=2;i<A;i++) {
        if (A%i==0)
            return false;
   
}
   return true;
}

@fishec · 20.09.2013, 22:51

Вообще достаточно от 2 до sqrt(A) искать делители.

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

C++

for (long long i=A ;i>1 ;i--) {
    if ((A%i==0)&&(isSimple(A)))
        result=i;
        break;
    }
}

@DmitryM5 · 20.09.2013, 22:51 **[ТС]**

Сообщение от fishec

Вообще достаточно от 2 до sqrt(A) искать делители.

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

C++

for (long long i=A ;i>1 ;i--) {
    if ((A%i==0)&&(isSimple(A)))
        result=i;
        break;
    }
}

Если число составное, то есть представляет собой произведение простых сомножителей, то среди этих сомножителей обязательно должен найтись хотя бы один, который будет меньше квадратного корня из заданного числа. Ведь произведение двух чисел, каждое из которых больше квадратного корня из некоторого X, будет заведомо больше X, и эти два числа никак не могут быть его делителями.

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

Черный экран теперь просто.

@fishec · 20.09.2013, 22:55

Сообщение от DmitryM5

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

тогда оно простое, и результат функции true

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

C++

for (long long i=A ;i>1 ;i--) {
    if (isSimple(i)&&(A%i==0))
        result=i;
        break;
    }
}

@DmitryM5 · 20.09.2013, 22:58 **[ТС]**

C++

#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 · 20.09.2013, 23:01 **[ТС]**

Нет,ошибка.

@fishec · 20.09.2013, 23:06

Сообщение от 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 · 20.09.2013, 23:06 **[ТС]**

Сообщение от fishec

тут ошибка isSimple должно быть от i

C++

#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 · 20.09.2013, 23:09

C++

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 · 20.09.2013, 23:19 **[ТС]**

Сообщение от fishec

C++

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++

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 · 20.09.2013, 23:31

C++

#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 · 20.09.2013, 23:37

DmitryM5, ты че, деревянный? Я тебе еще во втором посте сказал в чем у тебя проблема. Тебе гордость не позволяет это понять или что?
Если ты вообще ничего не понимаешь, то вот тебе решение:

C++

1 2	if ( flag ) return true; return false;

Надеюсь догадаешься куда вставить.
Это выражение можно легко заменить на: return !!(flag);

@DmitryM5 · 21.09.2013, 00:00 **[ТС]**

Сообщение от castaway

DmitryM5, ты че, деревянный? Я тебе еще во втором посте сказал в чем у тебя проблема. Тебе гордость не позволяет это понять или что?
Если ты вообще ничего не понимаешь, то вот тебе решение:

C++

1 2	if ( flag ) return true; return false;

Надеюсь догадаешься куда вставить.
Это выражение можно легко заменить на: return !!(flag);

Оловянный я.
Уже без флагов сделали,что тут не так тоже чтоли??

C++

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 · 21.09.2013, 00:10

В алгоритм я не вникал, но тут уже нет той проблемы, которую ты обозначил в теме.

@fishec · 21.09.2013, 00:37

Сообщение от DmitryM5

И этот ответ 600851475143=8462696833*71 не подходит...

Да алгоритм не правильный

@fishec 126 / 125 / 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

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	20.09.2013, 22:39	2
	А что непонятного? Функция isSimple не всегда может возвратить значение. 0

@DmitryM5 Консультант Витте 106 / 86 / 45 Регистрация: 27.08.2013 Сообщений: 1,356 Записей в блоге: 1
	20.09.2013, 23:01 [ТС]	11
	Нет,ошибка. 0

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	21.09.2013, 00:10	19
	В алгоритм я не вникал, но тут уже нет той проблемы, которую ты обозначил в теме. 0

@fishec 126 / 125 / 62 Регистрация: 07.09.2013 Сообщений: 343
	21.09.2013, 00:37	20
	Сообщение от DmitryM5 И этот ответ 600851475143=8462696833*71 не подходит... Да алгоритм не правильный 0