一个关于素数的性质

一 写在前面

1.1 本文内容

一个关于素数的性质。

二 素数性质

性质：所有大于等于5的素数一定和6的倍数相邻！此性质可以被证明，证明方法可以去搜索相关资料。下面给出1000以内的素数，你可以验证一下看是不是这样。

有了这个性质，下面再给出一个其在质因数分解中的实际应用例子。题目链接在此。题目大意是给定一个正整数N，要求将其分解成多个质因数相乘的形式。需要注意的是质因数分解的常用算法是试除法，例子中使用的也是试除法。并且每一个合数都能够写成几个质因数相乘的形式。

 质因数分解：http://oj.noi.cn/oj/#main/show/1170

上述题目的一个可行代码如下：

#include <stdio.h>
#include <stdbool.h>

int main(int argc, char *argv[])
{
    //freopen("in.txt", "r", stdin);
    int n, step;
    bool first = true;

    scanf("%d", &n);

    /* 将数n中包含的2, 3, 5这三个质因数给除去 */
    while (n % 2 == 0)
    {
        (first == true) ? printf("2") : printf("*2");
        first = false;
        n /= 2;
    }
    while (n % 3 == 0)
    {
        (first == true) ? printf("3") : printf("*3");
        first = false;
        n /= 3;
    }
    while (n % 5 == 0)
    {
        (first == true) ? printf("5") : printf("*5");
        first = false;
        n /= 5;
    }

    /* 让step从6开始，考察step相邻的两个数，如果能整除n，则将其除去 */
    step = 6;
    while (n >= (step-1))
    {
        if (n % (step-1) == 0)
        {
            (first == true) ? printf("%d", step-1) : printf("*%d", step-1);
            first = false;
            n /= (step-1);
        }
        else if (n % (step+1) == 0)
        {
            (first == true) ? printf("%d", step+1) : printf("*%d", step+1);
            first = false;
            n /= (step+1);
        }
        else
        {
            step += 6;
        }
    }

    putchar('
');
    //fclose(stdin);
    return 0;
}