判断一个大于 2 的正整数 n 是否为素数,请用至少两种方法实现。
时间: 2023-04-23 18:05:28 浏览: 1595
计算机二级C语言试题
方法一:试除法
判断一个大于 2 的正整数 n 是否为素数,可以采用试除法。即从 2 开始,依次将 n 除以 2 到 n-1 中的每个数,如果都不能整除,则 n 是素数;如果存在一个数可以整除,则 n 不是素数。
方法二:埃氏筛法
判断一个大于 2 的正整数 n 是否为素数,可以采用埃氏筛法。即先将 2 到 n 的所有数标记为素数,然后从 2 开始,将 2 的倍数标记为合数,再从 3 开始,将 3 的倍数标记为合数,以此类推,直到标记完所有小于等于 n 的数。如果 n 被标记为素数,则 n 是素数;否则,n 不是素数。
阅读全文