数论

数学问题

1. 质数筛

• 埃氏筛

利用当前已经找到的素数，从后面的数中筛去当前素数的倍数，由预备知识一可知，当前素数已经是筛去数的质因子，如此下去能筛除所有之后的合数，是一种比较快的筛法

bool st[N]; //如果为true则被筛掉，不是质数
int prime[N], cnt; //prime用于记录质数
void getprime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) //可以只筛出质数的倍数即可
        {
            prime[cnt++] = i;
            for(int j = i + i; j <= n; j += i)
                st[j] = true;
        }
    }
}

• 线性筛

  和埃氏筛法的区别是对于每一个要筛除的数，欧拉筛法只筛除一次，而埃氏筛法会重复筛除，比如8和16同时被2和4筛去，推荐使用欧拉筛法，维护一个质数表

  • 其中由于是从小到大枚举质数表，每个数一定被他的最小质因子筛掉

bool st[N]; //如果为true则被筛掉，不是质数
int prime[N], cnt; //prime用于记录质数
void getprime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

2.最大公约数与最小公倍数

利用辗转相除法即欧几里得算法递归求解，最大公约数则为两数相乘后除最大公约数

int gcd(int a, int b)
{
    return b ? gcd(b, a % b), a;
}  

//或者
int gcd(int a, int b)
{
    if(b == 0) return a;
    else return gcd(b, a % b);
} 
//或者
__gcd(a,b)
    
//最大公约数为
a * b / __gcd(a,b)

3.同余模定理

如对取模

typedef long long ll;
ll mod(ll n)
{
    ll s = n
    for(int i = 1; i < 5; i++)
    {
        s = ((s % 3) * (n % 3));
    }
    return s % 3
}

还有便是对大数进行取模，只能用字符串读入，利用进制转换时的数位分解进行求解

char s[1000];
int main()
{
    int n;//模n
    cin >> s;
    cin >> n;
    m = 0;
    for(int i = 0; i < strlen(s); i++)
        m = ((m * 10) % n + (s[i] - '0') % n) % n;
    //也可以加完后再取模，但会超出范围
    cout << n;
    return 0;
}