素数判定和素数筛

Posted on 2022-11-22 Edited on 2023-09-27 In 算法

素数判定

埃氏筛法

整体流程是从小到大遍历，并将利用小的因数将后面大的合数剔除掉
原理就是合数和素数的判定条件
边界条件就是不能超过n,可以从i*i开始比较
复杂度是O(nloglogn)
埃氏筛的时间复杂度为O(n log log n)，其中n是要筛选质数的范围。具体地，该算法的复杂度可以分为两部分：
1.标记合数的复杂度：O(n)。因为每个数最多只会被标记一次，而每个数最多有log log n个质因数，所以总共需要进行O(n log log n)次操作。
2.枚举质数的复杂度：O(n log log n)。因为每个质数最多只会被枚举一次，而n个数中质数的个数约为n/ln n，所以总共需要进行O(n/ln n)次操作。
因此，总的时间复杂度为O(n log log n)。

版本1

bool is_prime[N];
int Eratosthenes(int n) {
  int p = 0;
  //初始化标记数组,先标记成都是素数,后面是合数就擦掉
  for (int i = 0; i <= n; ++i) {
    is_prime[i] = 1;
  }
  is_prime[0] = is_prime[1] = 0;

  for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
      prime[p++] = i;  // prime[p]是
      if (i * i <= n && i*i > 0)//防溢出
      //i的倍数都是合数,实际上也是i*2,i*3，但由于在2-i-1时已经处理过了,
      //所以接下来从i*i,i*(i+1)=i*i+i,....
        for (int j = i * i; j <= n; j += i)
          is_prime[j] = 0;
    }
  }
  return p;
}

只筛奇数的版本

bool is_prime[N];
int Eratosthenes(int n) {
  int p = 0;
  for (int i = 0; i <= n; ++i){
    is_prime[i] = 1;
  } 
  is_prime[0] = is_prime[1] = 0;
  // i * i <= n 说明 i <= sqrt(n)
  //只需要筛一半
  for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i]) {
      prime[p++] = i;

      for (int j = i * i; j <= n; j += i)
        is_prime[j] = 0;
    }
  }
  return p;
}

只保留奇数的版本

is_prime可以只申请n/2一半，因为偶数肯定是合数

线性筛

如果能让每个合数只被标记一次，复杂度就来到了O(n)

void init(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) {
      pri[cnt++] = i;
    }
    for (int j = 0; j < cnt; ++j) {
      if ( (long long)(i * pri[j]) > n){
           break;
      } 
      vis[i * pri[j]] = 1;
      if (i % pri[j] == 0) {
        // i 之前被 pri[j] 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i乘上其他的质数的结果一定会被
        // pri[j]的倍数筛掉
        break;
      }
    }
  }
}

线性同余

Posted on 2022-11-22 Edited on 2023-10-09 In 算法

随机数

随机数一般可以用来仿真，抽样，生成测试数据来检验正确性。但生成真正的随机数是很难的，下面介绍一种伪随机数算法

线性同余伪随机数生成算法

序列周期取到模数n的称为满周期,c=0称为乘同余法, ,称为混合同余法

code实现

java中java.util.Random类的实现中，发生器的关键代码如下：

1
2
3

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;

private static final long multiplier = 0x5DEECE66DL;
    private static final long addend = 0xBL;
    private static final long mask = (1L << 48) - 1;

    //如果是32位int,则
    protected int next(int bits) {
        long oldseed, nextseed;
        //用的是long类型
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            //线性同余,mask就是模数,模数取的是2的幂次，所以取余可以这样取
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        //转成int型
        return (int)(nextseed >>> (48 - bits));
    }

    public int nextInt() {
        return next(32);
    }

混合同余法满周期的数学原理

定理1

由(模数m,乘数a,增量c和初始值x0)所确定的线性同余序列达到满周期当且仅当：

(c,m)=1
对m的任一素因子p,有
如果4|m则，

a=1的特殊情况

如果 $则同余式变成$ ,显然满足条件2和条件3.且同余式有较简单的表达式:

当 周 期 为 时 ， 有 并 且

又(c,m)=1,故 $又$
这样就证明了充分性.

必要性在a=1时，条件2和条件3是显然满足的,(c,m)互素由 $可知成立$

注意 a=1不具有随机性;

又在 $的情况下$ 根据同余性质,

故下面都假设

下面根据计算机程序设计艺术-第2卷-第3章论文中来介绍一下充分性和必要性,主要思想是得出递推式和x0的关系,将模数m做素数分解,这样会得到一个重要的简化定理，模数m的周期等于模数m素数分解得到的所有因数周期的最小公倍数.

引理1(得到递推式)

设是产生的随机数序列,且,则有

其中

特别的，取 ,即有

证:(用数学归纳法)
当n=0显然成立;
假设当n=k时成立,则当n=k+1时,有

令,即有

引理2(模数做素数分解)

设是线性同余产生的随机数序列,周期为,对m做素数分解,,其中为素数,.

记是由(初始值,乘子,增量,模数)为确定的随机数序列,周期为 ,其中 , 则有：

,即

为

的最小公倍数

证: 先证明素数分解只有2个数的情况,即
故， $两者互素$ ,

,由

定义知：

故根据同余性质,

即

,于是

.同理有

不妨设,下证：

一方面,由周期定义知,,则,由前面的结论知，,从而由周期的定义知,,同理,故有最小公倍数的定义知,,

另一方面,设 $为任一公倍数$ ,则由h是周期的倍数知

递 推 由 的 定 义 由 前 面 结 论

同理有,

综合上面2式，根据同余性质有

故有周期的定义知,,又 $是的任一倍数$ ,
故
对于素数分解2个以上的，由归纳法可知结论成立

引理3(一个数论结论)

设p为素数, $且$ ,

如果 $则$ .

证:(二项式定理展开)
由条件知, $其中且是素数$ ,从而有

其 中

显然,

因 $即当$ ,在组合数中总是可以分出一个p来,凑出这个因子(可分为p=2和p>2来讨论),所以p整除Q中带有组合数的项,但还有单独1这一项，

故

,故

引理4(一个数论结论)

如果 ,则:

对 任 意 都 成 立

证:

则，

于是可以仍然满足引理3的条件，继续应用引理3，得到:

其 中

即

下面证充分性,即要证:

对 任 意 都 成 立

对分子因式分解，化简有

由 命 题 条 件 知 令 可 有 同 余 和 整 除 等 价 性

同 理 对 于 每 个 都 可 以 提 出 一 个 总 共 有 项 但 可 以 多 提 出 一 个 故 总 共 可 以 提 出

因此充分性的得证.
必要性是显然的.因为 $肯定包含一个的因子$

引理5(化简到初始值为0)

由(模数m,乘数a,增量c和初始值x0)所确定的线性同余序列达到满周期当且仅当 $的周期为$
证:
必要性:比较显然，达到满周期的含义是不论x0的初始值是多少都是满周期

充分性: 设另有2个序列, $其中只有初始值不同是满周期$

由 于 和 的 取 值 都 在 之 间 并 且 每 个 值 都 只 会 出 现 一 次 ， 记 经 过 次 迭 代

则 由 周 期 定 义 即

引理6(递推式的性质)

设 $其中为素数$ ,如果

是 使 得 的 最 小 正 整 数 则

当 时 当 时

证:

必要性(用反证法):

$如果$ ,则有

因为,可利用同余和整除的等价性有:

又

,故

,于是当

时

由 同 余 和 整 除 的 等 价 性

但由费马定理知,

,这里和假设矛盾,

p=2时,如果 $则或者$

(1). 如果 ,根据同余和整除等价性,有

等式右边是奇数等式左边是偶数,矛盾
(2). 如果 ,则由引理4知, $这与是最小的矛盾$ ,必要性得证

充分性:
设对于引理中p=2和p>=2的情况，都满足引理3的条件,并且重复应用引理3,可有:

每 次 方 则 模 次 数 加 其 中

,又由引理3的证明过程中，

,令x=a,有

,故有

其 中

特别的,有

这个同余式表示, $是的倍数即$ ,故 $是这种形式又根据同余式知故$

备注
这个引理的充分性的证明在Hull和Dobell的论文Random Number Generators是通过二项式定理展开来证明的

说实话，这段整除性分析我没看懂。在高德纳的书中，是采用引理3的结论来证明的,可以发现，证明方法也是在基于新知识不断改进的

定理1的证明

终于来到主定理的证明了

由引理5,只需要考虑初始值为的情况,由引理1,可以得到一个简单的通项表达式,

由引理2知,只需要证明达到满周期即可,因为m的素数分解各个部分都是互素的,最小公倍数就是它们的乘积
下设

必要性:

用反证法,若 ,则设 $中的项都是位于中$ , 则可以取到1,即

但是 $不互素故而$
,导出矛盾,条件1证毕,接下来,引理5可将命题化简为要证明:
当 $时序列满周期$ .由引理6的必要性知,定理1的必要性成立.

充分性：

还是有引理5,可将命题充分性化简为要证明:
当 $时满足条件条件条件前提下有序列满周期$ .由引理6的充分性知定理1的充分性成立

线性同余统计检验

频数检测
目的是检测待测试二进制序列中，“0”和“1” 数目是否近似相等。
块内频数检测
目的是确定在待测序列中，所有非重叠的长度为M位的块内的“0”和“1”的数目是否表现为随机分布。
还有其他的很多检验指标

线性同余理论检验

待研究补充中

乘线性同余

先直接给出下面的定理,证明待后续补充。当c=0时，由定理1知，不会达到满周期.但选择合适的模数和乘数可以使周期达到m-1,在实际中已经够用了。这一个定理由高斯在他的算术研究中给出.

定理2

当c=0时,可能的极大周期为 ,如果:

x0与m互素
a是以m为模的原根
其中 $是的欧拉函数值$

注意如果m为素数,则可得到长度为m-1的周期

其他随机数算法

梅森旋转算法

总结

随机数这块理论其实很复杂的,尤其是理论证明.不得不膜拜高德纳老爷子的功底.那几本计算机程序设计艺术太难懂了,起码数学专业的博士才能读懂大部分.不过读书是这样的,需要当你把知识基础补充好之后,才能读懂.不过这本书的作者高德纳老爷子是图灵奖的获得者,读不懂也很正常。虽然读不懂，但还是尽量去读，学习顶尖数学家的思想和思维方式.可能TAOCP要我花一辈子去读了吧
读了文献之后，你发现其实一个理论的完善不是一代人搞出来的,是逐步完善. 一开始随机数只证明了的特殊情况,后面证明了充分性,到我们这代才完整的把充分必要性说清楚

引用

堆

Posted on 2022-11-22 Edited on 2023-10-07 In 数据结构

完全二叉树

每个节点一定是先有左孩子，再有右孩子.
当出现了叶节点之后，后续所有的节点都必须是叶节点。叶节点只可能会出现在倒数第一层和倒数第二层.

下标关系

1
2
3

父=(child-1)/2
左孩子=parent*2+1
右孩子=parent*2+2

实现

一般叫做堆，名字不重要，常用数组来实现，因为完全二叉树有良好的下标关系，可以把数组看成一颗树

jdk中的优先级队列

默认实现的是小根堆，PriorityQueue

支持修改元素字段的堆

但在修改堆中元素后无法保持序的特性,下面介绍这种改写堆的方法
主要是resign方法，找到元素对应的位置，同时向上和向下调整,复杂度为O(logn).Main方法中有对数器和使用方式

package org.kurt.datastructure.heap;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * 手写堆,支持修改元素的字段，并依旧保持堆的性质，
 * 插入O(logn),修改O(logn),修改元素字段O(logn)
 * 堆结构,实际上是完全二叉树,不过以数组形式存储。实现的是小根堆
 */
public class MyHeapType<T extends Comparable> {
    /**
     * 堆的大小
     */
    private int size;
    private ArrayList<T> arr;
    /**
     * 记录元素子啊堆中的位置
     */
    private HashMap<T,Integer> indexMap ;

    public MyHeapType(){
        arr = new ArrayList<>();
        indexMap = new HashMap<>();
    }

    public void push(T value) {
        heapInsert(value, size++);
    }

    public T pop() {
        if (size > 0) {
            swap(0, size - 1);
            T ans = arr.get(size-1);
            size--;
            heapify(0);
            return ans;
        }
        return null;
    }

    public T peek(){
        if(size>0){
            return arr.get(0);
        }
        return null;
    }

    /**
     * 修改堆中元素
     * @param t
     */
    public void resign(T t) {
        heapInsert(t, indexMap.get(t));
        heapify(indexMap.get(t));
    }

    /**
     * 把参数放到index位置
     * @param arr
     * @param index
     */
    private void heapify(int index) {
        //从index开始向下调整
        //调整到什么时候停
        int child = 0;
        while (index < size) {
            child = 2 * index + 1;
            if (child >= size) {
                break;
            }
            child = child + 1 < size && arr.get(child + 1).compareTo(arr.get(child))<0 ? child + 1 : child;
            if (arr.get(index).compareTo(arr.get(child)) > 0) {
                swap(index, child);
            } else {
                break;
            }
            index = child;
        }

    }

    private void swap(int a, int b) {
        T tmp = arr.get(a);
        arr.set(a, arr.get(b));
        arr.set(b, tmp);
        indexMap.put(arr.get(a), a);
        indexMap.put(arr.get(b), b);
    }

    /**
     * 向上调整
     * @param arr
     * @param value
     */
    private void heapInsert(T value, int index) {
        if(index >= arr.size()){
            arr.add(value);
        }else{
            arr.add(index, value);
        }
        indexMap.put(value, index);
        while (arr.get(index).compareTo(arr.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static class Student implements Comparable<Student>{
        public int score;
        public String name;

        public Student(int score, String name) {
            this.score = score;
            this.name = name;
        }

        /**
         *
         * @param o the object to be compared.
         * @return
         */
        @Override
        public int compareTo(Student o) {
            if (score > o.score) {
                return -1;
            } else if (score < o.score) {
                return 1;
            }
            return 0;
        }

        @Override
        public String toString() {
            return "Student{" +
                    "score=" + score +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

    public static void main(String[] args) {
        //对数器和系统的优先级队列做比对
        for (int i = 0; i < 1000; i++) {
            MyHeapType<Student> heapType = new MyHeapType<>();
            PriorityQueue<Student> queue = new PriorityQueue<>();
            int size = (int) (Math.random() * 1000);
            for (int j = 0; j < size; j++) {
                int score = (int) (Math.random() * 1000);
                Student tmp = new Student(score, "A" + score);
                heapType.push(tmp);
                queue.offer(tmp);
            }
            System.out.println(queue.peek() + "    " + heapType.peek());
            if (queue.peek() != heapType.peek()) {
                System.out.println(queue.peek() + "    " + heapType.peek());
                System.out.println("ERROR");
            }
        }
        System.out.println("PASS");

        MyHeapType<Student> heapType = new MyHeapType<>();
        Student a = new Student(100,"a");
        Student  b  = new Student(18,"b");
        Student c = new Student(30,"c");
        heapType.push(a);
        heapType.push(b);
        heapType.push(c);
        System.out.println(heapType.peek());
        //修改学生的分数,再调用resign,这样堆会重新做调整,系统堆做不到
        b.score=110;
        heapType.resign(b);
        System.out.println(heapType.peek());
    }

}