Notice
Recent Posts
Tags
- sequential logic circuit
- Algorithm
- structural modeling
- MUX
- 8bit timer/counter
- full adder
- ATMEGA128A
- Set
- atmega 128a
- atmega 128
- Recursion
- behavioral modeling
- gpio
- Method
- interface
- half adder
- Comparator
- fast pwm mode
- structure
- dataflow modeling
- behavior modeling
- normal mode
- interrupt
- java
- ctc mode
- timer / counter
- 4bit parallel adder
- verilog
- LED
- Linked List
목록Algorithm/알고리즘 공부 (6)
거북이처럼 천천히
효율적인 소수 판별법
이미 알고 있는 소수 판별법 이미 알고 있는 소수 판별법은 다음 두 가지 방법이었다. 문제 : 자연수 X이 소수인가? 반복문을 이용하여 자연수 X을 2 ~ X-1까지 나눠봐서 한 번이라도 나머지가 0인 경우가 나오면 자연수 X은 소수가 아니다. 약수는 쌍을 이룬다는 점을 이용하여 2 ~ X-1까지가 아닌 2 ~ X/2까지 나눠봐서 자연수 X이 소수인지 판별할 수 있다. 하지만, 2 ~ root(X)이하까지만 나눠봐도 해당 숫자가 소수인지를 효율적으로 판별할 수 있다고 한다. 직감적으로 "왜 root(X) 이하까지만 나눠도 되는가?"를 이해할 수 없어 수식적으로 증명해 보자 한다. 왜 root(X) 이하까지만 나눠도 되는가? 가정 : 자연수 X은 소수가 아닌 합성수이며, 자연수 X은 M * N으로 표현할 ..
Algorithm/알고리즘 공부
2022. 6. 18. 01:57