기본알고리즘 - 수학

문제1) 소수 판별하기 

소수란 : 1보다 크며 1과 자기자신만을 약수로 가지는 수 ex) 2(1,2) - 소수 O , 4(1,2,4) - 소수 X 

 

플로우차트)
1.3가지 변수선언 ( A - 소수인지 판별하기위해 입력받은수 , i - A보다 1작은수 , j - 2부터 i까지 1씩증가되는수) 
2. 소수인지 판별받을수를 하나 입력받는다 
3. j부터 i까지 반복문을 돌리면서 1과 자기자신이 아닌 수로 나우었을경우 나머지가 0이라면 소수가아니라고 출력한다 

 

방법1)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

int a;         int i;         boolean ck = true; //소수 판별여부(true면소수 false면 소수가아님)                   Scanner sc = new Scanner(System.in);         System.out.print("값입력");         a = sc.nextInt(); // C언어 - scanf("%d",&a); (정수형 변수 a에 10진수를 입력받음)                   i = a-1;                  for(int j=2;j<=i;j++) {             if(a % j == 0 ) { //해당 입력값을 1과자기자신이 아닌수로 나누었을때 나머지가 0이라면 소수가아님                  ck = false;                 break;             }         }                  if(ck != true || a == 1)  System.out.println("소수가 아닙니다");         else  System.out.println("소수입니다"); Colored by Color Scripter

cs

 방법2)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

int a;         int i;         int j=2;         Scanner sc = new Scanner(System.in);         while(true) {             a = sc.nextInt();             i = a - 1; //4가 입력되면 i는3이되고 4를 2,3으로 나누었을때 나머지가 0인지 아닌지를 판별              if(j<=i) {                 if(a % j == 0) {                     System.out.println("소수가 아님");                     break;                 }                 else j++;             }             else {                 System.out.println("소수가 맞습니다");                 break;             }         } Colored by Color Scripter

cs

방법3)

1.입력값을 j로 나누었을대 0이라면 while문을 빠져나감 
2.소수를 판별할 숫자 X를 2부터 차례대로 나누어서 떨어지지 않을때 J값 1씩증가
3. 입력값(a)와 제수(j)가 똑같으면 소수가 맞음 ex) 입력값 5 = j(5) 2,3,4 모두 나누어지는경우 없음 3번증가 + 초기값2

-> 즉..5의 소수를 판별할때 1과 자기자신(5)이 아닌 수로 나누었을때 총3번(2,3,4)나누어 떨어지지 않으면 j는 2에서 3번증가 하고 입력값(5) == J(소수를 판별할 변수-5) 똑같아지게 되므로 소수가 맞음 

1 2 3 4 5 6 7 8 9

int a,j=2;                  a = new Scanner(System.in).nextInt();           while(a % j != 0) {             j++;         }         if(a == j) System.out.println("소수가 맞음");         else System.out.println("소수가 아님");

cs

방법4) 제곱근을 이용한 소수판별식 

 

문제2) 소수의 합구하기 

 1.입력값(a) 변수필요
 2.2 부터 n까지 증가하는 변수(k)  - 소수인지 판별될 숫자가 저장되는 변수 
 3.소수의 합이 저장될 변수 (hap)
 4.소수를 판별할 변수(j)

문제3)소수의 개수 구하기 - 배열에 2~100사이의 정수를 기억시킨후 이배열을 이용해서 소수의 개수구하여라 

1.배열의 공간 생성

2. 2~100 사이의 정수를 기억시킴 2부터100까지 증가하는 변수필요 

3.배열에 저장된 값들로 소수의 개수를 구하기 

- 소수의 개수를 카운트 하는 변수 필요 (cnt)  int cnt = 0

- 소수인지 아닌지를 식별하는 변수(j) int j = 2

- 소수인지 판별할 숫자 2 ~ 100 (i) int i =0 

방법1)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

int[] array = new int[99];         int a = 2;         for(int i=0;i<array.length;i++) {             array[i] = a;             a++;          }                  int i=0,j=2,cnt=0;           while(i<=array.length-1) {               while(j<array[i]){                 //소수인지 아닌지 판별                  if(array[i] % j == 0) break;                 else j++;             }                          //소수일 경우실행              if(j == array[i]) cnt++;               i++;             j=2;           } Colored by Color Scripter

cs

방법2) 수열에서 처음나온 소수의 배수들은 소수가 아니라는 원리를 이용하자 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

int[] array = new int[8];         int a = 2;         for(int i=0;i<array.length;i++) {             array[i] = a;             a++;          }                                    int i=0,cnt=0;                          while(i<=array.length-1) {                          //소수인지 아닌지 검사 (0이라면 소수가 아니기 때문에 if문을실행안함)              if(array[i] != 0) {                  cnt++;                 //해당소수의 배수들의 모든값을 0으로 바꿈                  for(int k=i+array[i];k<array.length;) {                     System.out.println(array[k]);                     array[k] = 0; //array[2](4) = 0 , array[4] = 0 , array[6] = 0                     k = k + array[i];                  }             }                          i++;         } Colored by Color Scripter

cs

방법3)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

int[] array = new int[8];         int a = 2;         for(int i=0;i<array.length;i++) {             array[i] = a;             a++;          }                  int i=-1,cnt = 0;         int m;         while(true) {             i++;             if(i>array.length-1) {                  System.out.println("소수인개수"+cnt);                  break;             }             //해당 조건식을 만족할경우 아래있는 코드를 해석하지 않고 위로 올라감              if(array[i] == 0) continue;                          //소수일경우 실행              cnt++; //소수의 개수 1증가             m = i;                          while(true) {                 m += array[i];                 if(m > array.length-1) break;                 //해당소수의 배수들을 모두 0으로 바꿈                  array[m] = 0;             }                                   } Colored by Color Scripter

cs

문제4) 두수를 입력받아 두수의 최대공약수와 최소공배수를 출력하라 

최대공약수 : 두개이상의 자연수의 공통된 약수중에서 가장큰 공약수 

최소공배수 : 두개이상의 자연수의 공통된 배수중에서 가장큰 공배수 

참고사이트 : mathbang.net/202

최대공약수, 최대공약수 구하는 방법

방법1) 유클리드 호제법으로 풀기 

1. 입력받은 두개의 자연수중 큰수를 작은수로 나누어 나머지를 구함 

2. 나머지가 0이라면 이때의 작은수가 최대공약수 

3. 나머지가 0이 아닐경우 작은수를 큰수로 나머지를 작은수로 해서 나머지가 0이 될때까지 반복함 

ex) 5,12 -> 12/5 , 나머지 2 -> 5/2 ,나머지 1 -> 2/1 , 나머지 0 -> 1이 최대공약수가 됨 

4. 원래의 입력받은 두수를 곱한후 최대공약수로 나누어서 최소공배수를 구함 ( ( 5 * 12 ) / 1 -> 60 )

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

int a,b; //입력받을 두수          int m=0,n=0; //몫과 나머지(큰수와작은수를 저장할 변수)          int max; //최대공약수                   Scanner sc = new Scanner(System.in);         a = sc.nextInt();         b = sc.nextInt();                  //입력받은 두수중 큰수를 작은수로 나눔          if(a>b) {             m = a;             n = b;         }else {             m = b;             n = a;                 }                      //나머지가 0이라면 while문 탈출          while(true) {                  if(m % n == 0) break;             else{                 //작은수를 큰수로하고 나눈나머지를 작은수로함                  int temp = m; //큰수를 받을 임시변수 생성                  m = n; //작은수가 큰수에 대입되고 바뀐 큰수로 작은수를 나누면 안됨                   n = temp % n; // m % n (X)             }           }         max = n;         System.out.println("최대공약수"+max);         System.out.println("최소공배수"+(a*b)/max);

cs

문제5) 소인수 분해하기 

하나의 정수를 입력받아 소인수를 구해 출력해보자)

문제6) 10진수를 2진수로 변환하기 

 

방법1)

문제7)

N자리로 구성된 2진수를 입력받아 10진수로 변환하는 코드작성하시오

(단. N자리 2진수는 문자열로 되어있고 3번째 자리까지는 소수이상 4번째 자리부터 N번째 자리까지는 소수이하이다. )

문제8)

2의 보수 구하기 

방법1)

방법2) 이걸 기억하자 

문제9) 그레이 코드 변환하기 

이진수 -> 그레이코드) 

1.첫번째 그레이비트는 첫번째 이진수 비트를 그대로 내려씀 
2.두번쨰 그레이 비트부터 첫번째랑 두번째 이진수 비트를 XOR 연산해서 쓴다 
  -> XOR 연산 ( 연산하는 두개의 값이 같으면 0 다르면 1) 

그레이코드 -> 이진수) 

1.첫번째 이진수비트는 첫번째 그레이코드 비트를 내려쓴다 
2.두번째 이진수비트부터 왼쪽에 구해놓은 이진수비트(첫번째비트)와 두번쨰 그레이비트를 XOR연산해서 구한다 

문제10) 이진수 덧셈하기 

방법1) 정석 

방법2) 내가푼 방법