지환태

오랜만에 글 써보네요.
미안하지만 오늘 글은 모두 아는 소수 판단 알고리즘입니다. ㅈㅅㅈㅅㅈㅅ

소수 : 1과 자신 외에는 나누어 떨어지는 정수가 없는 양의 정수.

소수의 정의만 보면 2부터 n-1까지 나누어보아서 나누어지지 않으면 소수 나누어지면 소수가 아니라고 할 수 있습니다.

int prime(int n)
{
    int i;
    for(i=2;i<n;i++)
        if(n%i==0)
            return 0;

    return 1;
}

이 함수는 느리다. ㅡ,.ㅡ
소수를 판별할 때 n의 제곱근까지만 나누어 보면 된다고 한다.

16을 보면 16의 약수는 1*16, 2*8, 3*6, 4*4, 6*3, 8*2, 16*2 이렇게 앞 뒤가 서로 대칭된다.
그래서 제곱근을 구해주는 합수 sqrt(int)함수를 써보겠습니다.

int prime(int n)
{
    int i, sqrn;
    sqrn = (int)sqrt(n);
    for (i = 2; i <= sqrn; i++)
        if (n % i == 0)
            return 0;
 
    return 1;
}

 소수를 구하는 다른 알고리즘에는 에라토스의 체가 있습니다.
1부터 n까지의 소수를 구한다고 할 때 소수의 배수를 지워나가면서 남아있는 수를 구하는 알고리즘입니다.

main()
{
    int *arr;
    int i,j;

    arr=(int *)calloc(101,sizeof(int));//0부터 100까지 배열생성;

    for(i=2;i<=100;i++)
    {
        if(arr[i]==1)
        continue;

        j=i+i;
        while(j<=100)
        {
            arr[j]=1;
            j+=i;//i의 배수로 증가
        }
    }

    for(i=2;i<=100;i++)
        if(arr[i]==0)
            printf("%d ",i);
}

다음부턴 열심히 쓸게요. 때리지 마요 제발
이 글이 유익하다면 (굽신굽신) ->

버블정렬.
저음엔 이거만 있는 줄 알았는데.
지금은 GG상태.

Z	F	A	N	T	A
F	Z	A	N	T	A
F	A	Z	N	T	A
F	A	N	Z	T	A
F	A	N	T	Z	A
...	...	...	...	...	...

이런 식으로 비고하면서 정렬된다.
몇 번 더해야되.

#include <stdlib.h>  
#include <stdio.h>    
#include <time.h>    
#include <conio.h>  

int main()    
{    
    int a[100];    
    int start,end;    
    int max,min;    
    int count,count2;    
    int temp;  

    srand((unsigned)time(NULL));    

    printf("시작 : ");    
    scanf("%d",&start);    
    printf("종료 : ");    
    scanf("%d",&end);    

    min=end;    
    max=start;    

    printf("정렬 전\n");  
    for(count=0;count<20;count++)    
    {    
        a[count]=rand() % (end - start + 1) + start;                
        printf("%3d",a[count]);    
    }  

    /*여기부터*/ 
    for (count = 20-1; count > 0 ; count--)
    { 
        for (count2 = 1; count2 <= count ; count2++)
        {
            if (a[count2-1] > a[count2])
            {
                temp = a[count2-1];
                a[count2-1] = a[count2];
                a[count2] = temp;       
            }
        }
    }
    /*여기까지 거품정렬입니다.*/ 

    printf("\n정렬 후\n");  
    for(count=0;count<20;count++)    
    {    
        printf("%3d",a[count]);    
    }  

    getch();  
    return 0;    
}

참고 : 선택정렬


이거 좀 날로 먹는듯 ㅋㅋㅋ

이 글이 유익하다면 (굽신굽신) ->

오늘은 정렬중 쉽고 쉬운 선택정렬입니다.

아래 표는 정렬 과정.

	a[0]	a[1]	a[2]	a[3]	a[4]
1.	9	12	61	5	1
2.	1	12	61	5	9
3.	1	5	61	12	9
4.	1	5	9	12	61
5.	1	5	9	12	61

1. 배열중 가장 작은 값을 찾아 첫 번째 값과 위치를 바꿉니다.

2. 첫번째 값을 빼고 가장 작은 값을 찾아 두번째 값과 위치를 바꿉니다.

3. 첫번째,두번째 값을 제외하고 가장 작은 값을 찾아 세번째 값과 위치를 바꿉니다.

4. 다 될 때까지 반복 ㅡ,.ㅡ;;;

어때요

가장 쉬운 선택정렬입니다.

아래는 C언어로 만든 소스입니다.
예전 글 난수 발생함수 rand(), 난수 범위 지정하기의 소스도 썼습니다.

#include <stdlib.h>
#include <stdio.h>  
#include <time.h>  
#include <conio.h>

int main()  
{  
    int a[100];  
    int start,end;  
    int max,min;  
    int count,count2;  
    int temp;

    srand((unsigned)time(NULL));  

    printf("시작 : ");  
    scanf("%d",&start);  
    printf("종료 : ");  
    scanf("%d",&end);  

    min=end;  
    max=start;  

    printf("정렬 전\n");
    for(count=0;count<20;count++)  
    {  
        a[count]=rand() % (end - start + 1) + start;              
        printf("%3d",a[count]);  
    }

    /*여기부터*/
    for(count=0; count<20-1; count++) 
    { 
        min = count; 
        for(count2=count+1; count2<20; count2++) 
            if(a[count2] < a[min]) 
                min = count2;                  
        if(count != min) 
        {                    
            temp = a[min]; 
            a[min] = a[count]; 
            a[count] = temp; 
        } 
    } 
    /*여기까지 선택정렬입니다.*/

    printf("\n정렬 후\n");
    for(count=0;count<20;count++)  
    {  
        printf("%3d",a[count]);  
    }
    
    getch();
    return 0;  
}

이 글이 유익하다면 (굽신굽신) ->