使用算法:筛选法
问题:求素数
问题描述:
素数的定义:任何大于1的正整数,如果它不能被1和它本身之外的其它正整数整除,则该数为素数。
用筛选法求出素数。
问题分析:
所谓筛选法,即对于2~N之内的任一整数I,其倍数2×i,3×i,4×i,……,J×I(J×I<=N),都不是素数,可以筛选掉。I从2循环至N,逐个进行筛选,那么剩下的数就是2至N之间的全部素数。
比如找出50以内的所有素数,我们可以把50以内的所有数存放到一个一维数组中,把数I存放在S[I]中,对于I从2于50,如果S[i]>1,则可以把S[2*i],s[3*i],……,s[j*i]都筛选掉(清为0),当然J必须满足J×I<=50,最后输出数组中大于1的数(剩下的数)即可。
网友评论