一道面试题：用多线程求1000以内的素数有多少个？并给出消耗时间

首页 > 代码库 > 一道面试题：用多线程求1000以内的素数有多少个？并给出消耗时间

一道面试题：用多线程求1000以内的素数有多少个？并给出消耗时间

2024-08-18 13:25:33 220人阅读

我曾经去一个公司面试，遇到这么一个题目：求1000以内的素数有多少个？用多线程实现，并给出消耗时间。我想了半天，没有想出多线程的解决方案。今天因为机缘到了，我浅谈下我的解法。

这道题，显然得考虑两个问题：

1、多线程的问题

2、算法性能问题

有人觉得1000以内还考虑什么算法性能？这肯定很快。但是话说回来，这个都有必要用多线程吗？如果我们求10000000以内的素数有多少个？是不是必须考虑以上两个问题了？多线程和算法优化的目的都是为了提高程序执行的效率。我们首先来考虑算法问题，什么是素数？素数：也称为质数，在自然数中除了1和本身能整除外，没有其它数可以整除，并且1不是素数。比如2,3都是素数。好了，我们看代码：

 1           private static bool IsSushu1(int n) 2             { 3                 bool isSuFlag = true; 4                 if (n <= 1) return false; 5  6                 for (int i = 2; i < n; i++) 7                 { 8                     if (n % i == 0) 9                     {10                         isSuFlag = false;11                         break;12                     }13                 }14                 return isSuFlag;15             }

这是求一个数是不是素数的算法，此算法根据定义而来，如果面临千万级的数据，直接出不来结果。我们能不能优化下？答案是肯定的，所以数学学得好的话，对计算机工作者来说，总是有益无害，我们来看改进后的代码：

 1            private static bool IsSuShu(int n) 2             { 3                 bool isSuFlag = true; 4                 if (n <= 1) return false; 5  6  7                 for (int i = 2; i <= (int)Math.Sqrt((double)n); i++) 8                 { 9                     if (n % i == 0)10                     {11                         isSuFlag = false;12                         break;13                     }14                 }15                 return isSuFlag;16             }

代码没有大的改变，只是循环的次数大规模降低了，想一想，如果是百万级的数据，开个平方根，那就成了1000级别。这个算法的原理，还没有想明白，是从网上看到的，总之是实实在在的数学问题，如果数学思维很好的话，这个估计能想得来。

算法有了，那用多线程有哪些问题呢？

首先，我们每个线程的执行结果，必须拿到。其次，要算总的消耗时间。创建一个线程，我们可以直接用Thread创建，但是Thread创建比较消耗性能，而且要拿执行结果，也没法拿。如果用ThreadPool 创建后台线程的话，倒是性能提高了，还是直接拿不到线程执行的结果。我于是想到了c#中的Task。task知识点比较多，可以慢慢学习。先看实现：

 1             private static void MultiThreadCompute(int n,int pageSize) 2             { 3                 List<Task<int>> tasks = new List<Task<int>>(); 4  5                 var start = DateTime.Now; 6  7                 for (int i = 1; i <= n / pageSize; i++) 8                 { 9                     var pageIndex = i;10                     int startNum = (pageIndex - 1) * pageSize;11                     int endNum = startNum + pageSize;12 13                     int[] numbers = { startNum, endNum };14 15                     tasks.Add(Task.Factory.StartNew((obj) =>16                      {17                          int totalCount = 0;18 19                          int[] temps = obj as int[];20 21                          for (int j = temps[0]; j < temps[1]; j++)22                          {23                              if (IsSushu1(j))24                              {25                                  totalCount++;26                              }27                          }28                          return totalCount;29                      }, numbers));30                 }31 32                 Task.Factory.ContinueWhenAll(tasks.ToArray(), (taskList) =>33                 {34                     var end = DateTime.Now;35                     int result = 0;36 37                     foreach (var item in tasks)38                     {39                         result += item.Result;40 41                         Console.WriteLine("task{0}找到{1}个素数", item.Id, item.Result);42                     }43 44                     Console.WriteLine("{0}以内找到{1}个素数，总花费时间：{2}", n, result, end.Subtract(start).TotalSeconds);45 46                 });

解释下代码，pageSize就是我借鉴了网页上分页的算法，每个线程执行一个页的数据。从32行开始，这个是等所有的任务执行完毕，然后循环任务取得结果，也是异步调用，不会阻塞主程序的继续执行。这儿也可以改成同步调用：

 1               Task.WaitAll(tasks.ToArray()); 2  3                 int result = 0; 4  5                 foreach (var item in tasks) 6                 { 7                     result += item.Result; 8  9                     Console.WriteLine("task{0}找到{1}个素数", item.Id, item.Result);10                 }11 12                 Console.WriteLine("{0}以内找到{1}个素数", n, result);