Факторизация методом Ферма

@AlexProg · Регистрация: 03.11.2012

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

не пойму в чем проблема , реализую факторизацию методом Ферма , не пойму почему не работает

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
32
33
34
35
36
37
38
39
#include<iostream>
#include<clocale>
#include<cmath>
using namespace std;
void faktor(double n);
int POW(int k,int d);
int main()
{   
    double n=19691;
    faktor(n);  
    getchar();
    return 0;
}
void faktor(double n)
{
    double A;
    int m;
    int p;
    int q;
    int B;
    m = sqrt(n);
    for(int x=0;x<m;++x)
        A=m+x;
        B=sqrt(POW(A,2)-n);
        p=A+B;
        q=A-B;
        if(p*q==n)
        {
            cout<<"простые делитеои числа "<<n<<"числа "<<p<<" и "<<q;        
        }
}
 
int POW(int k,int d)
{
    int e=k;
    for(int i=0;i<d-1;++i)
        k=k*e;
    return k;
}

@Andrey1302 · 26.03.2018, 01:05

Там же все очень просто. Вот на си и на асме (вторая работает раза в 2-3 быстрее):

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
unsigned __int128 fer_c(unsigned __int128 n) {//Ферма__128 на С++
unsigned __int128 q=sqr128(n); __int128 a=q*q-n;
for(n=0;a!=0;) a>0 ? a-=(n++<<1)+1 : a+=(q++<<1)+1;
q==n ? q<<=1 : q-=n; if(q==1) return 0; return q;}
 
unsigned __int128 fer_asm(unsigned __int128 n) {unsigned __int64 ql=sqr128(n), qh;// Ферма__128 на asm
asm("xor %%rcx,%%rcx\n" "mov %%rbx,%%rax\n" "mul %%rbx\n" "sub %%rsi,%%rax\n" "sbb %%rdi,%%rdx\n" "xor %%rsi,%%rsi\n" "xor %%rdi,%%rdi\n"
".p2align 4\n" "MF128:\n" "test %%rdx,%%rdx\n" "jl MFS128\n" "jnz MFS0128\n" "test %%rax,%%rax\n" "jz RF128\n"
".p2align 4\n" "MFS0128:\n" "mov %%rsi,%%r8\n" "mov %%rdi,%%r9\n" "shl %%r9\n" "shl %%r8\n" "adc $0,%%r9\n" "add $1,%%r8\n" "adc $0,%%r9\n"
"sub %%r8,%%rax\n" "sbb %%r9,%%rdx\n" "add $1,%%rsi\n" "adc $0,%%rdi\n" "jmp MF128\n"
".p2align 4\n" "MFS128:\n" "mov %%rbx,%%r8\n" "mov %%rcx,%%r9\n" "shl %%r9\n" "shl %%r8\n" "adc $0,%%r9\n" "add $1,%%r8\n" "adc $0,%%r9\n"
"add %%r8,%%rax\n" "adc %%r9,%%rdx\n" "add $1,%%rbx\n" "adc $0,%%rcx\n" "jmp MF128\n"
"RF128:\n" "cmp %%rdi,%%rcx\n" "jne MRF128\n" "cmp %%rsi,%%rbx\n" "jne MRF128\n" "shl %%rcx\n" "shl %%rbx\n" "adc $0,%%rcx\n" "jmp EF128\n"
"MRF128:\n" "sub %%rsi,%%rbx\n" "sbb %%rdi,%%rcx\n"
"EF128:\n" :"=c"(qh),"=b"(ql): "S"((unsigned __int64)n),"D"((unsigned __int64)(n>>64)),"b"(ql));
n=qh; n=(n<<64)+ql; if(n==1) return 0; return n;}

@perevertysh · 26.03.2018, 01:22

вы тут всей группой перед семинаром отрываетесь?

Факторизация больших чисел

Факторизация числа

Новые блоги и статьи Все статьи Все блоги /
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .

@perevertysh 5 / 5 / 6 Регистрация: 23.03.2018 Сообщений: 98
	26.03.2018, 01:22
	вы тут всей группой перед семинаром отрываетесь? Факторизация больших чисел Факторизация числа 0