就没有一个简便的方法找出质数和合数吗

投稿:心岛初晴 优质问答领域创作者 发布时间:2023-10-24 18:15:11
就没有一个简便的方法找出质数和合数吗

找出质数和合数的最简便方法是使用素数筛法。首先,创建一个长度为n+1的布尔数组,将所有元素初始化为true。然后从2开始,将其倍数(除自身外)在布尔数组中标记为false。接下来,遍历布尔数组,所有值为true的索引即为质数,而所有值为false的索引即为合数。该方法的时间复杂度为O(n log log n),其中n为给定范围内的最大整数。这种方法简单易懂,高效快速地找出质数和合数。