OpenMP并行计算程序设计-n以内的完数的个数 柔光的暖阳◎ 2022-07-16 11:50 150阅读 0赞 # 1.问题描述 # 一个数如果恰好等于它的因子之和,这个数就称为“完数”。例如6=1+2+3,再如8的因子和是7(即1+2+4),8不是完数。输入一个数n,编程找出n以内的所有完数及其个数。 # 2.算法设计 # ## 2.1 串行算法设计 ## 串行算法步骤如下 ①因为1不算入一个完数,所以令数i=2,初始化答案值ans=0; ②因为1是任何数的一个因数,所以可初始化因数之和sum=1; ③令数k=2; ④如果数i能整除数k,说明k是i的一个因数,则sum += k; ⑤若k<=i/2(控制范围保证i%k能进行计算),++k,转到④,否则转到⑥; ⑥若sum = i,++ans; ⑦若i <=n,++i,转到②,否则转到⑧; ⑧函数返回答案值ans。 ## 2.2 并行算法设计 ## 并行算法步骤如下 ①因为1不算入一个完数,所以令数i=2,初始化答案值ans=0; ②“\#pragmaomp parallel for” ②因为1是任何数的一个因数,所以可初始化因数之和sum=1; “\#pragmaomp parallel for” ③令数k=2; “\#pragmaomp critical” ④如果数i能整除数k,说明k是i的一个因数,则sum += k; ⑤若k<=i/2(控制范围保证i%k能进行计算),++k,转到④,否则转到⑥; ⑥若sum = i,++ans; ⑦若i <=n,++i,转到②,否则转到⑧; ⑧函数返回答案值ans。 ## 2.3 理论加速比分析 ## 若p个处理器上数据量为n,则S=np/(n+2plogp)。 本机测试中,p=4:若n=10000,则S=3.9981;若n=100000,则S=3.9998。 /*问题描述:一个数如果恰好等于它的因子之和,这个数就称为“完数”。例如6=1+2+3,再如8的因子和是7(即1+2+4),8不是完数。编程找出n以内的所有完数。 */ // test.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <cstdlib> #include <iostream> #include <cmath> #include <ctime> #include <omp.h> #include <windows.h> using namespace std; int OMP_Perfect(long long n) //并行计算n以内的完数个数 { int ans = 0; // n以内的完数个数 long long i, k; //循环变量 #pragma omp parallel for for (i = 2; i <= n; i++) //1不算入一个完数。 { long long sum = 1; //数的因数之和,1是任何数的一个因数。 #pragma omp parallel for reduction(+:sum) //解决sum数据冲突 for (k = 2; k <= i / 2; k++) //k<=i/2是要保证i%k能进行计算。 if (i%k == 0) sum += k; //因数之和 if (sum == i) //找到一个完数 ++ans; //函数返回答案值ans } return ans; } int Perfect(long long n) { int ans = 0; // n以内的完数个数 long long i, k; //循环变量 for (i = 2; i <= n; i++) //1不算入一个完数。 { long long sum = 1; //数的因数之和,1是任何数的一个因数。 for (k = 2; k <= i / 2; k++) //k<=i/2是要保证i%k能进行计算。 if (i%k == 0) sum += k; //因数之和 if (sum == i) //找到一个完数 ++ans; //函数返回答案值ans } return ans; } int main() { long long n; cin >> n; printf("%lld以内的完数有:\n", n); clock_t t1, t2; t1 = clock(); printf("Sum= %d\n", OMP_Perfect(n)); //输出并行计算出的n以内的完数个数 t2 = clock(); printf("parallel time: %d\n", t2 - t1);//输出并行计算时间 t1 = clock(); printf("Sum= %d\n", Perfect(n)); //输出串行计算出的n以内的完数个数 t2 = clock(); printf("serail time: %d\n", t2 - t1); //输出串行计算时间 system("pause"); return 0; } ![20161017211922946][] ![20161017211935931][] [20161017211922946]: /images/20220716/781a9433e0b6418f9e72f4a59fad11c3.png [20161017211935931]: /images/20220716/64675041e4ae44fe9f3c594940e40a46.png
还没有评论,来说两句吧...