선별 법 소수
4744 단어 알고리즘
(1) 준비: 길이 가 10000 인 배열 isPrime 을 1 로 초기 화 합 니 다.
(2) 선별: i 는 2 에서 100 까지 한다. i 가 소수 라면 i 의 배 수 를 그 어 낸다. 즉, isPrime [2 * i], isPrime [3 * i].
(3) 출력: i 는 2 에서 10000 까지 합 니 다. 만약 에 isPrime [i] = 1 이면 i 는 소수 이 고 출력 합 니 다.
생각: 왜 한 단계 의 순환 은 i 가 2 에서 100 이 아니 라 i 가 2 에서 10000 까지 입 니까?순환 횟수 감소, 연산 속도 증가
#include<stdio.h>
#include<math.h>
#define N 10000
int isPrime[N+1];
void initPrime()
{
int i, k, m;
for(i=1;i<=N;i++) isPrime[i]=1; /* */
m=(int)sqrt(N);
for(i=2;i<=m;i++) /* */
{
if(isPrime[i]==1)
for(k=i+i;k<=N; k=k+i)// i
isPrime[k]=0;
}
}
int main()
{
int i;
initPrime();
for(i=1;i<=N;i++) /* 10000 */
{
if(isPrime[i]==1)
printf("%5d",i); // i isPrime[i]
}
return 0;
}
/* ， */
#include<stdio.h>
#include<math.h>
#define N 10000
/* N ， prm ， */
int prime (int prm[])
{
int i, prmNum, n;
int isPrime[N+1]; /* */
for(i=0; i<=N; i++) /* isPrime 1*/
isPrime[i]=1;
n = (int)sqrt(N);
for(i=2; i<=n; i++)
{
if(isPrime[i]) /* i */
{
for(int j=2*i; j<=N; j=j+i) /* */
isPrime[j]=0;// isPrime[i] = 0
}
}
for(prmNum=0,i=2;i<=N;i++) /* IsPrime */
{
if(isPrime[i]==1) /* i ， prm*/
prm[prmNum++]= i ;
}
return prmNum; /* */
}
int main()
{
int i, prmNum, prm[N];
prmNum=prime(prm); /* , prmNum */
for (i=0;i<prmNum;i++) /* 10000 */
{
printf("%5d",prm[i]);
if(prmNum%10==0) /* 10 */
printf("
");
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
