[学习笔记]Pollard-rho算法

一.什么是Pollard-rho

​ 这是一个用来寻找一个合数的因子的算法。很显然的,我们可以使用试除法，1~\(\sqrt{n}\)之间一个一个试。很显然他很慢。

二.朴素的代码

​ 我们来看一个沙雕代码。

    n=read();
    int a=rand()%(n-2)+2;
    if(n%a==0)cout<<"I found "<<a;
    else cout<<"I'm such a stupid.";

​ 很显然的，这段代码很沙雕，完全就是在碰运气抽签。在这