c언어 질문입니다

qw3709의 이미지

소수 3797에는 왼쪽부터 자리수를 하나씩 없애거나 (3797, 797, 97, 7) 오른쪽부터 없애도 (3797, 379, 37, 3) 모두 소수가 되는 성질이 있습니다.

이런 성질을 가진 소수는 단 11개만이 존재합니다. 이것을 모두 찾아서 합을 구하세요.

(참고: 2, 3, 5, 7은 제외합니다)

이게문제이고요

저번에도 한번 올렸는데 도움받고 혼자해볼려고 하루종일 이것만 붙들고 해봤는데 수가큰지 아무리 기다려도 답이안나오네요...
어디가 잘못됬는지 한번 찾아주시면 감사하겠습니다.
제눈에는 틀린부분은 안보이거든요... 아직 초보라

#include <stdio.h>
#include <math.h>
int judgesosu(int nums)
{
	int div_num,jud=0;
 
	if(nums%2==0)
	return 0;
	else
	for(div_num=3;div_num<sqrt(nums);div_num+=2){
 
		if(nums%div_num==0){
		jud=1;
		break;
		}
	}//소수찾기
	if(jud != 1)
	return 1;
	else
	return 0;
 
}//소수인지 판별하는 함수 
int getsosu(int num)
{
	int size=1,disnum=0;
	long long clone_num=0,ret_val=0,test=0;
 
	clone_num=num;
 
 
 
	while(clone_num>9){
		clone_num=num/10;
		size*=10;
	}//자리수구허기 
 
	clone_num=num;
 
	while(clone_num>9){
		clone_num=clone_num/10;
		if(judgesosu(clone_num))
		ret_val=1;
		else
		return 0;
	}//오른쪽 부터 뺴기 
 
	clone_num=num;
 
	while(clone_num>9){
		clone_num=clone_num-((num/size)*size);
		size=size/10;
		if(judgesosu(clone_num))
		ret_val=1;
		else
		return 0;
	}//왼쪽부터 빼기 
 
 
	if(ret_val==1)
	return 1;
 
 
 
}//어디로든 빼도 소수가 되는지 확인하는 함수  
void main()
{
	unsigned long long total=0,find_num=10;
	long long divis,judge=0,count,select=0;
 
	for(;;)//전체 반복문
	{
		find_num+=2;
		 for(divis=3;divis<=sqrt(find_num);divis+=2)
		 {
		  	 if(find_num%divis==0){
		  	 judge=1;
		  	 break;
		  }
		  	 if(judge != 1){
		  	 	select=getsosu(find_num);
		 		 if(select==1){
		 			 total+=find_num;
		 			count+=1;
					}
		 	}//답인지아닌지 판별 
		 }//소수를 찾기위한 반복문
 
		 select=0;
 
		 if(count==11)
		 break;
 
 
 
	} //count가 11이 될떄까지 소수를 계속 찾는 함수  
 
	printf("%lld",total);
 
 
}
raymundo의 이미지

저번에도 말씀드렸지만, 특정한 일만 전담하는 함수를 만들었다면 그 함수가 정말 제대로 동작하는지도 확인해보셔야 합니다. 그 확인을 하지 않은채로 이 함수를 이용하는 코드를 만들면 더더욱 버그를 잡기 어려워질 뿐입니다.

1) 현재 judgesosu()는 1을 소수라고 잘못 판정합니다. 2를 소수가 아니라고 잘못 판정합니다.

2) 현재 judgesosu()는 홀수의 제곱수(9, 25, 49, ...)들을 소수라고 잘못 판정합니다. for 루프에서 sqrt(nums)보다 작다가 아니라 작거나 같다로 조건을 주세요.

3) main에서 find_num = 10 으로 시작해서 2씩 증가하고 있으니 지구가 멸망할 때까지도 답을 찾지 못하겠네요. 11부터 시작하게 하면 1)번 문제 때문인지 13을 답으로 판정해버리네요.

4) 지난 번에도 말씀드렸지만 일단 3797을 제대로 11개의 답 중 하나로 판정해낼 수 있는지부터 검사하세요. 나머지 10개가 뭔지 자신도 모르는데 프로그램으로 찾아내려고 하니까 검증이 더 힘들지요.

5) main 함수의 로직이 매우 이상합니다. 본문 코드의 들여쓰기가 제대로 되어 있지 않아서 착각하게 되는데,

// 이미 judgesosu 함수가 있는데 왜 여기서는 굳이 다시 루프를 돌며 나누는지도 이상하고요.
        for(divis=3;divis<=sqrt(find_num);divis+=2)
        {
            if(find_num%divis==0){
                judge=1;
                break;
            }
 
 
 
// 이 if 단락이 for 루프 안쪽에 있는 게 맞는지 생각해보세요.
// 아직 이 시점에는 find_num이 소수인지 아닌지 확정되지 않았습니다.
// (단지 방금 divis 로는 나누어 떨어지지 않았다는 것만 알 수 있을 뿐. 나누어 떨어졌다면 break걸려서 탈출해버렸을 테니)
// 예를들어 find_num이 53이라면(이건 11개의 수 중 하나)
// divis 가 3일 때 아래 단락을 수행해서 합격하니 total에 더하고
// divis 가 5일 때 아래 단락을 수행해서 합격하니 total에 더하고
// divis 가 7일 때 아래 단락을 수행해서 합격하니 total에 더하고
// ...
// 이 단락은 for 루프가 종료된 후에 수행하도록 빼내세요.
            if(judge != 1) {
                select=getsosu(find_num);
                if(select==1){
                    total+=find_num;
                    count+=1;
                }
            }//답인지아닌지 판별 
        }//소수를 찾기위한 반복문

6) 한 번이라도 judge 가 1이 되어 버리면 그 다음부터는 계속 1이니까, find_num이 몇이 되든 저 getsosu 검사를 하지 않고 넘어가버립니다. find_num +=2 를 할 때마다 judge도 0으로 리셋해주세요.

7) getsosu 들어가자마자 자리수 구하는 데부터 문제가 있습니다.

// num 이 3797일 때
 
	while(clone_num>9){
		clone_num=num/10;
// 백날 돌아도 clone_num = 3797 / 10 = 379 니까 이 루프는 끝나지 않습니다.
// clone_num = clone_num / 10; 으로 고치세요.
		size*=10;
	}

8) 오른쪽부터 빼기 루프는 문제가 없는 것 같고요. 왼쪽부터 빼기를 보면

// 3797 로 시작했을 때
     clone_num=clone_num-((num/size)*size);  // 첫 루프에서 797이 되는 건 맞는데
     clone_num=clone_num-((num/size)*size);  // 797 - ( ( 3797/100 ) * 100 ) = 797 - 3700 = -2903
// clone_num / size 로 고치세요.

9) 저번에도 지적했지만 이번에도 getsosu 함수의 경우 ret_val이 1이 아닌 경우 무슨 값을 반환할지 알 수 없는 상태가 됩니다. return 0 명시적으로 넣으세요.

제가 빠뜨린 게 있을지 모르겠는데, 여기까지 고치면 아마 답이 나올 겁니다. 11번째 수는 739397 라서 그렇게 크지 않습니다. long long을 쓸 필요도 없이.

다시 말씀드리지만, 다 만들고 나서 테스트하려고 하지 마세요. 걷잡을 수 없습니다.

1) 어떤 수가 소수인지 판정하는 judgesosu 를 만들었으면, 그 함수부터 올바른 결과를 내는지 확인하세요. 1~20 정도까지 루프를 돌면서 그 수를 어떻게 판정하는지 보면 되겠지요.

2) getsosu 를 만들 때도 size를 구하는 코드를 만들었으면 수를 몇 개 넣어가면서 정말 size가 제대로 나오는지 확인하고 진행했다면 훨씬 쉬웠을 겁니다.

3) 오른쪽 왼쪽에서 제거해가며 테스트할 때도, 매 루프마다 clone_num 을 printf로 출력시켜서 정말 제대로 제거해나가는지 볼 수 있습니다.

4) 그러고나면 이미 아는 답(3797이나, 쉽게 떠올릴 수 있는 23, 53 같은 거나, 반대로 답으로 판정되면 안 될 123 같은 것)을 넣어서 제대로 결과가 나오는지 보고요.

5) main 함수에서도 해당되는 수를 찾을 때마다 덜렁 합만 구하게 하지 말고 그 수를 출력시켜서 정말 맞는 수만 찾고 있는지 보세요.

좋은 하루 되세요!

qw3709의 이미지

답이다르게나옵니다

qw3709의 이미지

매번 감사합니다..
말씀하신 내용 다읽고 고쳐봤는데 답이 13,17,31,37,53,71,73,113,131,137,173 이렇게나오네요

raymundo의 이미지

그 말은 13 이 getsosu(13)에 들어가서 1을 반환한다는 얘기지요.

그런 잘못된 판정을 하는 이유는 코드 어딘가에 잘못된 로직이 들어있다는 얘기고, 그것을 어떻게 잡아낼지도 위에 다 적어드렸습니다.
제가 보기에는 여전히 1을 소수라고, 2는 소수가 아니라고 잘못 판정하고 있는 것 같네요.

좋은 하루 되세요!

raymundo의 이미지

문제점을 찾으며 고치다보니 결국 완전히 수정하게 되어서... 원래 작성하셨던 것과 비슷한 형태로 만들었으니 비교해보시면 좋을 것 같습니다.

그리고 이게 어디 올라온 문제인지는 모르겠는데, 아마 일일이 find_num을 2씩 증가하며 찾는 것보다 훨씬 더 빠르게 답을 찾아내는 게 목표였을 것 같네요. 예를 들어 일의 자리의 수는 오직 3과 7밖에 안 될 거고요.

#include <stdio.h>
#include <math.h>
 
// num이 소수인지 판별
// 소수이면 1반환
// 아니면 0반환
int judgesosu(int num)
{
    int div_num;
 
    // 1은 소수가 아님
    if ( num == 1 )
        return 0;
 
    // 2는 소수
    if ( num == 2 )
        return 1;
 
    // 그 외 짝수는 모두 합성수
    if ( num % 2 == 0 )
        return 0;
 
    for ( div_num = 3; div_num <= sqrt(num); div_num += 2 ){
        if ( num % div_num == 0 ) {
            // 한번이라도 나눠지면 합성수이니 여기서 끝
            return 0;
        }
    }
 
    // 여기까지 왔다면 한번도 나눠진 적 없다는 얘기니까 소수
    return 1;
}
 
// num이 조건에 맞는 수인지 검사
int getsosu(int num)
{
    int size = 1;
    int clone_num;
 
    clone_num = num;
 
    while ( clone_num > 9 ) {
        clone_num = clone_num/10;
        size *= 10;
    }
 
    //오른쪽 부터 뺴기
    clone_num=num;
    while(clone_num>9){
        clone_num=clone_num/10;
        if ( ! judgesosu(clone_num) )
            // 한 번이라도 소수가 아니면 더 볼 필요 없으니 여기서 종료
            return 0;
    }
 
    //왼쪽부터 빼기
    clone_num=num;
    while(clone_num>9){
//        clone_num=clone_num-((clone_num/size)*size);
//      잘 생각해보면 위 식은 결국 clone_num을 size로 나눈 나머지
        clone_num = clone_num % size;
        size=size/10;
        if ( ! judgesosu(clone_num) )
            return 0;
    }
 
    return 1;
}
 
 
int main()
{
    int total=0,find_num=11,count=0;
 
    while ( count < 11 )
    {
        find_num+=2;
 
        if ( ! judgesosu( find_num ) ) {
            continue;
        }
 
        if ( getsosu( find_num ) ) {
            printf("FOUND %d\n", find_num);
            total+=find_num;
            count+=1;
        }
    }
 
    printf("total = %d\n",total);
 
    return 0;
}

좋은 하루 되세요!

qw3709의 이미지

어제오늘 사이트접속이안됬네요... 저 댓글달고 10분뒤에 답구했는데 739397까지 마지막수가나오는데 딱 10개네요

qw3709의 이미지

위코드 참조해서 해결해보겠습니다 감사합니다

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.