모바일 오유 바로가기
http://m.todayhumor.co.kr
분류 게시판
베스트
  • 베스트오브베스트
  • 베스트
  • 오늘의베스트
    		•
    유머
  • 유머자료
  • 유머글
    		•
    이야기
  • 자유
  • 고민
  • 연애
  • 결혼생활
  • 좋은글
  • 자랑
  • 공포
  • 멘붕
  • 사이다
  • 꿈
  • 똥
  • 군대
  • 밀리터리
  • 미스터리
  • 술한잔
  • 오늘있잖아요
  • 투표인증
  • 새해
    		•
    이슈
  • 시사
  • 시사아카이브
  • 사회면
  • 사건사고
    		•
    생활
  • 패션
  • 패션착샷
  • 아동패션착샷
  • 뷰티
  • 인테리어
  • DIY
  • 요리
  • 커피&차
  • 육아
  • 법률
  • 동물
  • 책
  • 지식
  • 취업정보
  • 식물
  • 다이어트
  • 의료
  • 영어
  • 맛집
  • 추천사이트
  • 해외직구
    		•
    취미
  • 사진
  • 사진강좌
  • 카메라
  • 만화
  • 애니메이션
  • 포니
  • 자전거
  • 자동차
  • 여행
  • 바이크
  • 민물낚시
  • 바다낚시
  • 장난감
  • 그림판
    		•
    학술
  • 경제
  • 역사
  • 예술
  • 과학
  • 철학
  • 심리학
    		•
    방송연예
  • 연예
  • 음악
  • 음악찾기
  • 악기
  • 음향기기
  • 영화
  • 다큐멘터리
  • 국내드라마
  • 해외드라마
  • 예능
  • 팟케스트
    		•
    방송프로그램
  • 무한도전
  • 더지니어스
  • 개그콘서트
  • 런닝맨
  • 나가수
    		•
    디지털
  • 컴퓨터
  • 프로그래머
  • IT
  • 안티바이러스
  • 애플
  • 안드로이드
  • 스마트폰
  • 윈도우폰
  • 심비안
    		•
    스포츠
  • 스포츠
  • 축구
  • 야구
  • 농구
  • 바둑
    		•
    야구팀
  • 삼성
  • 두산
  • NC
  • 넥센
  • 한화
  • SK
  • 기아
  • 롯데
  • LG
  • KT
  • 메이저리그
  • 일본프로야구리그
    		•
    게임1
  • 플래시게임
  • 게임토론방
  • 엑스박스
  • 플레이스테이션
  • 닌텐도
  • 모바일게임
    		•
    게임2
  • 던전앤파이터
  • 롤
  • 마비노기
  • 마비노기영웅전
  • 하스스톤
  • 히어로즈오브더스톰
  • gta5
  • 디아블로
  • 디아블로2
  • 피파온라인2
  • 피파온라인3
  • 워크래프트
  • 월드오브워크래프트
  • 밀리언아서
  • 월드오브탱크
  • 블레이드앤소울
  • 검은사막
  • 스타크래프트
  • 스타크래프트2
  • 베틀필드3
  • 마인크래프트
  • 데이즈
  • 문명
  • 서든어택
  • 테라
  • 아이온
  • 심시티5
  • 프리스타일풋볼
  • 스페셜포스
  • 사이퍼즈
  • 도타2
  • 메이플스토리1
  • 메이플스토리2
  • 오버워치
  • 오버워치그룹모집
  • 포켓몬고
  • 파이널판타지14
  • 배틀그라운드
    		•
    기타
  • 종교
  • 단어장
  • 자료창고
    		•
    운영
  • 공지사항
  • 오유운영
  • 게시판신청
  • 보류
    		•
    임시게시판
  • 메르스
  • 세월호
  • 원전사고
  • 2016리오올림픽
  • 2018평창올림픽
  • 코로나19
  • 2020도쿄올림픽
    		•
    • 게시판찾기
    • 게시물ID : programmer_897
    작성자 : 엔델
    추천 : 3
    조회수 : 1784
    IP : 182.223.***.2
    댓글 : 4개
    등록시간 : 2014/01/29 11:04:47
    http://todayhumor.com/?programmer_897 모바일
    [팁] O(1) 소수 판별 함수.
    제가 prime ring problem (이하 PRP) 문제를 구현하면서, 
    가장 속도가 느린 부분은, 어떤 수가 '소수이냐 아니냐?'를 판별하는 것이었습니다.

    일반적인 소수 판별 알고리즘은, 간단하게는 그냥 나눠 보는 것 부터 시작해서, 여러 알고리즘이 존재합니다.

    그런데 PRP 에서는 n<=16 이라는 제한 조건이 있으므로, 16+15 = 31 까지의 소수만 판별하면 됩니다.
    이런 경우 정말 단순 무식하게 구현하는게 최곱니다.

    int is_prime(int n)
    /* return value
    -1 : invalid input range
     0 : not prime number
     1 : prime number
    */
    {
    static int prime_number[] = 
    {0,  0,1,1,0,1,0,1,0,0,0, 1,0,1,0,0,0,1,0,1,0, 0,0,1,0,0,0,0,0,1,0, 1};
    if ((n<0) || (n>31) return -1;
    return prime_number[n];
    }

    이렇게 구현하면 정말 O(1) 만에 소수 판별이 가능하지요.

    여기서는 함수로 구현하고, 에러 체크까지 했지만, PRP 문제에서는 그런것 다 필요 없으니 빼버리고, 
    실제로도 코딩은 함수가 아니라 매크로 형태로 구현해 버리면 됩니다.

    ............

    이런 극단적인 방법은 소수 범위가 정말 극한적으로 작을때나 가능합니다.

    그런데, 정말 이렇게 구현해 버리면, 더 큰 n 에 대해서 처리가 안되니깐,
    다른 데서 사용하기 위해서는 더 일반적이 경우를 고려해서 작성해야 합니다.

    좀더 일반적으로 32비트 정수 범위(42억 이하)에서는 대략 다음과 같은 방법을 사용합니다.

    1) 65536 크기를 가지는 배열 prime_number[] 을 만든다.
    2) 1 ~ 65536 까지 고전적인 방법인 '에라토스테네스의 체'를 이용해서 소수를 모두 구하여, 소수이면 1 아니면 0 을 채운다.
    3) 이 배열에서 소수가 몇개인지 세어, 소수 배열 prime_sequence[] 을 만든다.  (주1 : 655개)
    4) 위의 65K 배열에서 하나씩 찾아서 소수 배열 prime_sequence[] 에 집어 넣는다.
    (주2 : 결과적으로 int prime_sequence[] = { 2, 3, 5, 7, 11, 13, 17, ...} 이란 배열을 만드는 것)

    5) 만약 입력 값이 65536 보다 작으면, 배열 prime_number[] 을 이용해서 바로 답을 내준다.
    6) 만약 입력 값이 65536 보다 크고 42억보다 작으면, prime_sequence[] 을 이용해서 655번 나눠보면 소수 판정이 가능하다.
    (주3: 사실 이 범위의 대부분은 합성수이기 때문에, 2, 3, 5 ,7, 11, 13, 17 로 정도로 나눠보는 것만으로도 99%의 수는 합성수로 판별 가능함.)

    참고로 prime_number[] 배열은 메모리가 허용하는 한도에서 조금 더 키우면, 약간의 속도 향상을 얻을 수 있습니다.
    실제 사용할 때는 보통 100만개 정도 배열을 잡아서 100만 이하의 소수라면 바로 판별할 수 있도록 합니다.

    ...............

    32비트 정수를 넘어가는 수에 대해서 애초에 그런 수를 다루는 것 부터가 귀찮아 집니다.
    C 에서는 GMP 라이브러리를 사용하거나 ( https://gmplib.org/ )
    JAVA 에서는 BigInterger 클래스를 써야 하지요. ( http://docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html )

    문제는 이런거 쓰는 순간, 모든 코딩을 처음부터 다시해야 해서,  일반적인 알고리즘 문제에서는 신경쓰지 않습니다.

    ................

    참고로 JAVA 의 IntInterger 글래스에는 '확률적으로 소수인지 판정하는 isProbablePrime() 이란 기기묘묘한 메소드가 존재합니다.

    - 엔델 -


    이 게시물을 추천한 분들의 목록입니다.
    [1] 2014/01/29 15:21:11  122.38.***.234  REGENTAG  141650
    [2] 2014/01/29 15:21:56  121.130.***.238  뢍  194613
    [3] 2014/01/30 05:24:52  219.250.***.64  리습  380706
    푸르딩딩:추천수 3이상 댓글은 배경색이 바뀝니다.
    (단,비공감수가 추천수의 1/3 초과시 해당없음)

    죄송합니다. 댓글 작성은 회원만 가능합니다.

    번호 제 목 이름 날짜 조회 추천
    23441
    		예전에는 함수 하나에 대한 기능에 고민을 많이 했는데.. ssonacy 24/05/21 09:45 739 0
    23440
    		c++ 에서 DB 쿼리문처럼 사용할 방법이 있을까요? [8] 상사꽃 24/05/19 11:10 861 0
    23439
    		쉬운 배터리 알림 창작글 언젠가아자 24/05/14 10:47 1065 0
    23438
    		아후 서터레스 NeoGenius 24/04/02 17:52 890 1
    23436
    		로또 [3] 까망사투리 24/03/11 15:53 1414 4
    23434
    		copilot 기업유료버전 intelliJ에 붙여서 쓰고있는데 지리네요 안녕월드 24/02/22 00:15 1463 0
    23433
    		코딩마을 대나무숲 [7] cocoa 24/02/20 14:50 1605 5
    23432
    		(질문) 프로그래머분들은 싱글PC게임 레벨제한 풀수 있죠?? [22] 본인삭제금지 할배궁디Lv2 24/02/13 13:36 1652 1
    23431
    		Freemium NeoGenius 24/02/13 13:23 1188 0
    23429
    		부산에서 프로그래머 구인하는데 연봉 6천에서 8천 작은건가 [3] 폴팡 24/02/04 20:50 1861 1
    23427
    		chatgpt? bard? [4] 별빛러브 24/01/25 06:24 1312 0
    23426
    		Next.js로 만들어봤어요~ [3] 창작글 sonnim 24/01/24 12:52 1472 3
    23425
    		Spring Boot 공부하기 - 한국투자증권 오픈API 호출 옐로우황 24/01/21 17:51 1430 1
    23424
    		파이썬 코딩 관련해서 질문드립니다. [4] 투투나 24/01/08 09:49 1617 0
    23423
    		9년차 개발자의 "나만의 챗봇" 만들기 with ChatGPT [2] 아자뵤옹 23/12/10 22:35 1815 4
    23420
    		이 에러가 뭘까요? [2] +.푸른바다.+ 23/11/03 15:25 1952 1
    23419
    		[유니티 코리아] MWU 2023 투표하고 푸짐한 경품 받아가세요! engine1 23/10/06 18:52 1529 0
    23418
    		Flutter로 만든 채팅 어플리케이션 with ChatGPT 아자뵤옹 23/09/13 22:39 2037 0
    23417
    		특정 페이지 직접 접근 어떻게 막으시나요? [9] 달콤아시타 23/09/10 09:36 2063 0
    23416
    		버츄얼 유튜버가 완성한 '세계 최초' 애플 실리콘 GPU 드라이버 펌글 우가가 23/09/02 23:52 2171 2
    23415
    		뜨끈뜨끈한 30분짜리 삽질 [9] 창작글 상사꽃 23/08/29 16:00 2463 1
    23414
    		[유니티 코리아] MWU 코리아 어워드 2023 마감 임박! mwuaward2023 23/08/26 14:01 1630 0
    23413
    		[유니티 코리아] MWU 코리아 어워드 2023 mwuaward2023 23/08/13 19:52 1668 0
    23412
    		React.js 공부하기 - REST API 호출(CRUD) 옐로우황 23/08/05 13:13 1919 0
    23411
    		영어앱을 만들었는데, 사용자들의 의견 받고 싶습니다! [2] 맑은바다13 23/08/03 18:28 1884 2
    23410
    		진짜 절박해서 정말 ㅠㅠ 첫끼간절해서 도움주실분ㅠ.. [3] 명금123 23/07/17 22:28 1978 0
    23409
    		[유니티 코리아] MWU 코리아 어워드 2023 mwuaward2023 23/07/04 16:49 1773 0
    23407
    		라즈베리파이 파이썬코드에 while문 썼는데 동작을 안해요 [3] 싱그러운햇살 23/06/17 17:18 2053 1
    23405
    		라즈베리파이, 스위치 하나 누르면 다른 스위치들도 반응해요 [3] 싱그러운햇살 23/06/15 22:39 2097 1
    23403
    		혹시.. 중소기업 재취업 목표.. 공부방법 및 툴 버전 질문드려도 될까요 [2] 베스트금지베오베금지외부펌금지 웃대메템 23/06/13 01:46 2207 0
    [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [다음10개▶]
    단축키 운영진에게 바란다(삭제요청/제안) 운영게 게시판신청 자료창고 보류 개인정보취급방침 청소년보호정책 모바일홈