关于linux:OS大作业二多线程程序测试一个数是否为完全数

题目：

如果一个数 N 的所有因数（不包含 N 自身）的和还是 N，则 N 是一个齐全数。如果一个数 N 的所有因数（不包含 N 自身）的和还是 N，则 N 是一个齐全数，如 6 和 28，输出是一个整数 N，如果 N 是齐全数则输入 true，否则输入 false。主程序从命令行读取数字 N 和 P，创立 P 个线程，将 1~N 这 N 个数分给各个线程，保障两个线程不会分到雷同的数。每个线程判断这些树是不是 N 的因数，如果是，那么放到一个共享的缓冲区中。在父过程中用适合的同步办法期待所有的线程执行结束后，判断 N 是否是齐全数，即判断是否 N 的所有因数之和还是 N（提醒：你能够将测试的数限定在 1 至 N 的平方根来减速计算过程。）

思路

• 首先，题目只要求判断 一个 数是否为齐全数，并且要求通过多线程实现，那么每次线程进行的都只是齐全数的子问题：找出 N 的因数。即判断 N%cnt==0 是否为零。若为零，阐明 cnt 是 N 的因数，将其统计到和 sum 当中。
• 错误想法：只是单纯的创立 N 个线程让每一个线程顺次判断 1 …N- 1 是否为 N 的因数。
• 纠正：线程能够有很多个，应该让多个线程去抢夺 子问题 的执行，但又必须保障各线程不能同时执行子问题而造成同一个因数被屡次计算。因而， 必须对子问题进行加锁解决。

void* isFactor(void* args){while(/* 线程期待条件 */){pthread_mutex_lock(&mutex);
        
        // 判断是否为因数
        
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

• 保障 1 …N- 1 不会被反复判断：各个线程会抢夺 mutex_lock，但同一时刻只能有一个线程在执行子问题。因而咱们设定一个值 cnt，来代表 1 …N- 1 这些数。并且cnt 的变动只能在锁内进行，这就保障了 1 …N- 1 中的每个数只会被执行一次。

• 线程期待与完结条件： sum！= N 之前，所有线程都未完结，并且只有一个线程在拜访锁，此线程拜访完结后开释锁资源，再与其余线程一起抢夺锁资源。每次抢夺锁资源的线程数是始终不变的，始终都是创立的线程数。 sum == N 之后，所有线程同时完结。因而，线程期待条件为 sum != N 。

  int cnt = 1,sum = 0;
  void* isFactor(void* args){while(sum != N){pthread_mutex_lock(&mutex);
        
        if(N % cnt == 0){sum += cnt;}
        cnt++;
        
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
  }
  

优化

依据题目提醒，若 n 是 N 的因数，则 N / n 也肯定为 N 的因数。因而，实际上最多只需

$$
\sqrt{N}
$$

次判断即可。因而程序可批改为：

int cnt = 2,sum = 1;
void* isFactor(void* args){while(cnt < sqrt(N)){pthread_mutex_lock(&mutex);
        
        if(N % cnt == 0){sum = sum + cnt + N/cnt;}
        cnt++;
        
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

残缺代码如下：

#include <stdio.h>
#include <pthread.h>
#include <math.h>

#define MAX_N_thread 1000
#define TRUE 1
#define FALSE 0


int N;
int cnt = 2,sum = 1;
pthread_mutex_t mutex=PTHREAD_MUTEX_INITIALIZER;

void* isFactor(void* args){while(cnt < sqrt(N)){pthread_mutex_lock(&mutex);
        
        if(N % cnt == 0){sum = sum + cnt + N/cnt;}
        cnt++;
        
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

int main() {pthread_t th[MAX_N_thread];
    
    
    int P,NArray[MAX_N_thread];
    printf("Input N and P:");
    scanf("%d%d",&N,&P);
    
    //creat P threads
    for(int i = 1;i <= P;i++){pthread_create(&th[i], NULL, isFactor, NULL);
    }
    

    for(int i = 1;i <= P;i++){pthread_join(th[i], NULL);
    }
    
    
    printf("sum = %d",sum);
    return 0;
}