Algorithm Find a prime

알고리듬 Find a prime을 알아보겠습니다.

​
소수는 1과 자기 자신으로 만 나눠지는 수를 말합니다.
0과 1은 소수가 아닙니다.
​
소수를 구할 때에는 약수의 성질을 이용합니다.





약수의 경우 대칭되는 값이 존재합니다.

따라서, 우리는 소수를 확인하기 위해 1에서 26까지 전부 확인할 필요 없이 1과 2만 확인하면 13, 26을 확인한 것과 똑같습니다.

​

그렇다면, 이 절반을 어떻게 찾을 수 있을까요?

바로 제곱근(root)을 사용합니다.

약수가 저렇게 대칭되지만, 제곱근의 경우 대칭되는 수가 자기 자신이기 때문입니다.

​

26의 경우 대략 5입니다.




따라서, 1~ 5까지만 확인하면 됩니다.

​

​

​

코드로 한 번 봅시다.

1 보다 작으면 False

2와 3이면 True

그 외에는 12번째 줄처럼 math.sqrt를 이용해서 절반까지만 확인하면 됩니다.













끝.



카테고리: Algorithm

세계적인 앱 개발자(The world-class application developer)
반구저기(反求諸己)

댓글

댓글 쓰기

궁금한 점은 댓글 달아주세요.
Comment if you have any questions.

이 블로그의 인기 게시물

음악 총보(Score), 파트보(Part)

이미지
사용 프로그램 : MuseScore 3 ​ 총보와 파트보에 대해서 알아보겠습니다. ​ 총보는 모든 악기들의 보표가 표시된 악보입니다. 보표의 악기 순서는 다음과 같습니다. 목관악기, 금관악기, 타악기, 독주 악기(피아노, 하프), 현악기 ​ 파트보는 자신이 연주하는 악기에 대한 보표만 존재하는 악보입니다. ​ 총보(score) 파트보(part) 위의 악보에서 Flute 1은 첫마디를 한 뒤, 31마디는 아무 음도 없습니다. 그래서 뒤에 31로 숫자 적힌 긴 막대로 표시됩니다. ​ Flute 2의 경우는 앞 2마디를 쉬고, 연주하고, 뒤 29마디를 쉽니다. 끝. 카테고리: Music
자세히 보기 »

Python urllib.parse.quote()

이미지
사용 버전: Python 3.6.8 사용 프로그램: Atom 1.40.1 x64 ​ 파이썬 urllib.parse.quote()에 대해서 알아보겠습니다. 괄호 안에는 string, safe, encoding, errors 인자가 들어갑니다. ​ urllib.parse.quote()는 아스키코드 형식이 아닌 글자를 URL 인코딩 시켜줍니다. ​ String 인자에는 string, bytes 형식이 들어갑니다. String 형식. Bytes 형식 Safe 인자에는 URL encoding에서 제외할 문자를 넣습니다. 기본으로 '/'이 설정되어 있습니다. Encoding 인자에는 인코딩 이름이 들어갑니다.  string에 들어가는 문자와 맞지 않으면 오류가 나옵니다. 기본적으로 'utf-8'이 들어갑니다. Error 인자에는 'strict', 'ignore', 'replace', 'xmlcharrefreplace', 'backslashreplace', 'namereplace', 'surrogateescape', 'surrogatepass'가 들어갑니다. 기본적으로 strict가 설정되어 있습니다. unicode 오류를 알려줍니다. Ignore의 경우 오류는 무시하고, 변환할 수 있는 것만 변환합니다. Replace는 에러 글자를 '?'로 변환해줍니다. 그리고 quote(...
자세히 보기 »

KiCad 시작하기 6 (FreeRoute 사용하기 1)

이미지
사용 버전: KiCad 5.1.4 ​ 오늘은 KiCad의 숨겨진(?) 기능, 지금은 비활성화가 된 기능 Freeroute 또는 Autoroute를 해보겠습니다. ​ 먼저, Freeroute 기능을 사용하려면, Java JDK를 설치해야 합니다. Freeroute 기능은 Java 파일이기 때문입니다. ​ 저는 NetBeans IDE를 사용하겠습니다. License 수락을 하고, 운영체제에 맞는 실행파일을 내려받습니다. 받은 파일을 실행합니다. 다음으로 Freeroute 코드를 내려받습니다. https://github.com/nikropht/FreeRouting 압축을 풀어서 적당한 위치에 둡니다. (한글 경로는 피해주세요.) ​ ​ 자바 도움 파일인 jh.jar 파일을 아래 사이트에서 내려받습니다. https://github.com/kellertuer/Gravel/blob/master/javahelp/jh2.0/javahelp/lib/jh.jar 내려받은 jh.jar 파일을 적당한 위치에 둡니다.(한글 경로는 피해주세요.) 이제, 설치된 NetBeans IDE 8.2를 실행합니다. File-New Project를 누릅니다. Java - Java Project with Existing Sources를 누르고 Next를 누릅니다. 이름을 변경해주고, 저장 위치를 원하는 곳으로 설정합니다. Add Folder...를 누릅니다. 압축을 푼 FreeRouting-master를 찾아 열기를 누릅니다. 추가된 것을 확인하고, Next를 누릅니다. Finish를 누릅니다. 프로젝트를 우 클릭하여, Properties를 누릅니다. Libraries를 누르고, Add JAR/Folder를 누릅니다. ...
자세히 보기 »

Kivy 시작하기 12 (Pyinstaller로 exe 파일 만들기)

이미지
사용 버전: Python 3.6.8, Kivy 1.11.1 사용 프로그램: Atom 1.43.0 x64 ​ 기획: URL 소스 자료를 내 컴퓨터에 저장하는 앱. ​ 파이썬 파일을 exe 파일로 만들어 보겠습니다. PyInstaller를 사용합니다. ​ pip로 설치합니다. pip install pyinstaller ​ 설치가 다 되었으면, 확인해봅니다. 잘 설치되었네요. ​ 자, 만들어 봅시다. Shift + 마우스 오른쪽을 눌러 프로젝트가 있는 창에 PowerShell을 엽니다. cmd를 쳐서 cmd를 실행합니다. ​ ​ python -m PyInstaller --name [exe 파일 이름] [메인 python 파일 위치] ​ 다시 명령어 창이 뜨면, 진행이 다 된 것입니다. ​ ​ dist와 build 폴더가 생기고, spec 파일이 생깁니다. ​ URL Download.spec 파일을 열어줍니다. ​ coll 부분을 다음과 같이 수정합니다. ​ ​ 저장 후, 다시 pyinstaller를 사용합니다. ​ 기존의 파일이 사라진다는 경고문이 나오는데, y를 눌러줍니다. ​ ​ 완료되면, dist 폴더로 가서 Download.exe를 실행합니다. ​ ​ 실행이 됩니다. ​ 하지만 Location을 누르면, 정상 작동하지 않고 꺼집니다. 이를 해결하려면, 다시 만들어야 합니다. cmd로 실행해보면, 이러한 문구가 나옵니다. 모듈 win32timezone이 없다. ​ ​ spec에 추가해줍니다. hiddenimports에 적어줍니다. ​ ​ 다시 pyinstaller로 exe 파일을 만듭니다. 잘 작동되는 것을 확인할 수 있습니다. ​ 끝. ​ 앱: https://play.google.com/store/apps/details?id=starlight.jaehwa.one 코드: https://github.com/shwoghk14/Kivy_for_Starter 카테고리: BlackSmith,...
자세히 보기 »

일본어 문장부호

일본어 문장부호를 알아보겠습니다. ​ ​ 우리나라 대한민국에서 사용하는 문장부호들과 비교해보겠습니다. ​ 한국의 작은따옴표('')를 일본에서는 낫표(「」)로 표시합니다.  한국의 큰따옴표("")를 일본에서는 겹낫표(『』)로 표시합니다. 한국의 쉼표(,)를 일본에서는 모점(、)으로 표시합니다. 한국의 마침표(.)를 일본에서는 고리점(。)으로 표시합니다. 한국의 느낌표(!)를 일본에서는 고리점(。)으로 표시합니다. 한국의 물음표(?)를 일본에서는 고리점(。)으로 표시합니다. ​ ​ 일본에는 마침표, 물음표, 느낌표가 모두 고리점으로 표시되기 때문에 잘 생각해서 문장을 이해해야 할 것 같네요. ​ ​ 끝. 카테고리: 언어 공부 ​
자세히 보기 »

Android 특정 SDK Version 설정하기

이미지
사용 버전: Android Studio 4.0.1 사용 언어: Kotlin 1.3.72 안드로이드 특정 SDK Version 설정하기를 해보겠습니다. ​ 안드로이드 API에는 Level이 존재합니다. 안드로이드 버전에 따라 사용 가능한 level이 다릅니다. ​ 아래의 경우 현재 SDK 최소 버전은 21인데, 사용하고자 하는 API는 23이라서 사용할 수 없다고 오류가 나온 상태입니다. 두 가지 해결 방법이 존재합니다. 하나는 app 용 build.gradle의 minSdkVersion을 23으로 수정하는 방법입니다. 위의 방법은 고작 API 하나 때문에 포기해야 하는 Android 버전이 많아집니다. ​ ​ 다른 하나는 23 이상인 버전에서만 작동되게 만드는 것입니다. Build.VERSION.SDK_INT를 사용하여 버전을 체크합니다. 위의 사진처럼 하게 되면, 낮은 버전에서는 위의 API가 작동하지 않고, 높은 버전에서만 작동되게 됩니다. ​ 끝. 카테고리: Android
자세히 보기 »

KiCad 시작하기 4 (기존 회로도 수정 및 추가)

이미지
사용 버전 : 5.1.0 kicad 기존 회로도 수정 및 추가에 대해서 알아보겠습니다. ​ 'Schematic Layout Editor'를 눌러줍니다. 아래의 화면이 나옵니다. '키보드 A'를 누릅니다. 우리가 추가한 소자가 보입니다. 적당한 위치에 놓습니다. 전원을 연결할 커넥터도 추가해줍니다. 적당한 위치에 놓습니다. 시멘트 저항을 지나는 LED 회로를 추가하겠습니다. LED를 복사합니다. '키보드 C' 이번엔 직접 전선 연결 말고, 레이블 기능을 사용해 보겠습니다. '키보드 L'을 누릅니다. 적당한 이름과 크기를 설정하고, 확인을 누릅니다. 다음과 같이 놔둡니다. '키보드 C'로 복사를 해서, 맞은편 LED에도 붙여줍시다. '키보드 R'로 회전 가능합니다. 'Label'기능은 같은 이름을 가진 것끼리 전선으로 연결해줍니다. 선이 복잡하게 있으면, 보기 힘들기 때문에 Label을 많이 사용합니다. 나머지 부분은 다음과 같이 똑같이 만들어주세요. 'Assign PCB footprints to schematic symbols'를 눌러줍니다. ​ 'Annotate'를 누릅니다. 다음과 같은 창이 나옵니다. 'View selected footprint'를 누르면, footprint를 미리 볼 수 있습니다. 적당한 footprint를 설정해줍니다. 확인을 눌러줍니다. 'Perform electrical rules check'를 눌러줍니다. 'Run'을 누릅니다. 이상이 ...
자세히 보기 »

Android Compose Hilt

이미지
사용 언어: Kotlin 1.9.0 사용 버전: Android Studio Hedgehog 2023.1.1 Patch 1 안드로이드 컴포즈 Hilt를 알아보겠습니다. Hilt는 DI(Dependency Injection, 의존성 주입)를 편하게 하기 위한 라이브러리입니다. Dagger라는 DI 라이브러리를 Android에 사용하기 편하게 수정한 게 Hilt입니다. 공식 사이트입니다. https://dagger.dev/hilt/ 참고 프로젝트: https://github.com/Jaehwa-Noh/Practice-Amphibians/tree/compose-hilt-amphibians-app 우선, 이러한 dependencies가 필요합니다. app 용 build.gradle에 현재 필요한 두 개만 적어줍니다. implementation("com.google.dagger:hilt-android:2.50") kapt("com.google.dagger:hilt-compiler:2.50") kapt를 인식하지 못하네요. Project 용 build.gradle로 갑니다. kotlin("kapt") version "1.9.0"을 적어줍니다. 그 후, app 용 build.gradle로 와서 kotlin("kapt")를 적어줍니다. 그리고 밑에 kapt를 적고 correctErrorTypes = true를 적어줍니다. Sync now를 눌러주세요. 간편하게 사용하기 위한 Hilt Gradle Plugin을 추가해 줍시다. project 용 build.gradle로 갑니다. id("com.google.dagger.hilt.android") version "2.50" apply false 추가해 줍니다. app 용 build.gralde로 갑니다. id("com.google.dagger.hilt.android") enableAggreg...
자세히 보기 »

Python urllib.request.urlopen()

이미지
사용 버전 : Python 3.6.7 사용 프로그램 : Atom 1.33.1 x64 ​ 파이썬 urllib.request.open()에 대해서 알아보겠습니다. 괄호 안에는 url, timeout 속성이 들어갑니다. ​ urllib.request.urlopen()은 HTTP 연결을 할 때 사용합니다. HTTP/1.1을 사용하며,  괄호 안에는 url 또는 request object를 사용할 수 있습니다. https://docs.python.org/3/library/urllib.request.html#urllib.request.Request 'url' 속성에는 URL encoding 된 주소가 들어갑니다. 네이버 페이지를 여는 코드를 짜보았습니다. ​ 실행하면, 위와 같이 네이버의 html을 읽어 들입니다. ​ ​ timeout 속성을 사용하면, 연결 대기 시간을 정할 수 있습니다. 서버 측에서 응답이 없거나 늦을 시, 해당 대기시간이 지나면 우리가 연결을 끊습니다. 우리나라는 인터넷 시설이 좋기 때문에, timeout 시간을 0.01초 정도 설정해야 끊기는 걸 볼 수 있습니다. 여기서 주의할 점은 오류 메시지를 띄우면서, 프로그램이 종료된다는 점입니다. 따라서, try, except를 사용하시기 바랍니다. ​ ​ 끝. 카테고리: Python, urllib [계수기] 앱 광고 외국: Hand Counter  ​ https://play.google.com/store/apps/details?id=starlight.jaehwa.handcounter 계수기 앱. 하나씩 개수를 셀 때 사용해보세요. 센 ...
자세히 보기 »

KiCad 시작하기 7 (FreeRoute 사용하기 2)

이미지
사용 버전: Kicad 5.1.4 ​ 저번 시간에 이어서 Freeroute를 사용해보겠습니다. ​ 각 PCB 제조사마다 디자인 룰이란 것이 존재합니다. 우리는 그것에 맞추어서 선이나 구멍을 만들어줘야 합니다. ​ 디자인 룰 설정을 합시다. 우선 PCB Layout Editor을 실행합니다. 파일 - Board Setup을 누릅니다. Design Rules - Net Classes를 누릅니다. 위의 창에서 디자인 룰을 설정합니다. '+'를 눌러 디자인 룰을 새롭게 만들든지, 기존의 Default를 변경하든지 편하신 대로 조정해줍니다. ​ 유격: 선과 선 사이 간격 트랙 두께: 선 굵기 Via Size: Via 납 지름 비아 드릴: Via 구멍 지름 uVia Size: 모름 uVia Drill: 모름 dPair Width: 모름 dPair Gap: 모름 ​ ​ 저는 Power Class를 추가하여, +5V와 GND에 Assign To Selected Nets로 한꺼번에 적용시켰습니다. 나머지 전선은 Default Class 적용을 받고, +5V와 GND만 Power class 적용을 받습니다. ​ Ctrl + S로 저장을 한 번 해줍니다. 파일 - 내보내기 - Specctra DSN... 을 눌러줍니다. 적당한 위치에 dsn 파일을 저장합니다. NetBeans에서 Autoroute를 실행합니다. Open Your Own Design을 눌러, 아까 저장한 dsn 파일을 불러옵니다. Autorouter를 눌러줍니다. 전선 긋기, 최적화하기 순으로 진행되고, 완료가 되면, Postroute completed라는 문구가 나옵니다.전선 긋기나 최적화 중 마우스 왼쪽 버튼을 누르면, 그 상태로 정지됩니다. 최적화가 필요 없으면, 정지 후 바로 PCB에 사용하셔도 됩니다. File - Export Specctra S...
자세히 보기 »