Prime 숫자 프로그램
https://stackoverflow.com/questions/502443
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
내가 하려는 현재 어떤 질문을 연습하는 내 프로그래밍 능력입니다.(지 그것이 학교에서는 아직 아무것도,자)가르치는 이 문제는 나에게 필요한 읽는 숫자에게 txt 파일이다.이 번호는 것 N.지금 내가 가정을 찾을 수 있 N 번째 소수 위 N <=10 000.내가 찾은 후에,내가 가로 인쇄를 다른 txt 파일입니다.지금 대부분의 질문에 나가하거나 이해할 수 있는 방법을 고안하여 얻 N.문제는 나는 배열을 사용하여 저장하 이전에 발견 prime 번호를 사용하도록을 확인하기 위해 그들에 대하여 미래의 숫자입니다.을 때에도 내가 배열의 크기는 100 만큼,입력된 정수 거 < 15,프로그램에 충돌.
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
int main() {
ifstream trial;
trial.open("C:\\Users\\User\\Documents\\trial.txt");
int prime;
trial >> prime;
ofstream write;
write.open("C:\\Users\\User\\Documents\\answer.txt");
int num[100], b, c, e;
bool check;
b = 0;
switch (prime) {
case 1:
{
write << 2 << endl;
break;
}
case 2:
{
write << 3 << endl;
break;
}
case 3:
{
write << 5 << endl;
break;
}
case 4:
{
write << 7 << endl;
break;
}
default:
{
for (int a = 10; a <= 1000000; a++) {
check = false;
if (((a % 2) != 0) && ((a % 3) != 0) && ((a % 5) != 0) && ((a % 7) != 0)) // first filter
{
for (int d = 0; d <= b; d++) {
c = num[d];
if ((a % c) == 0) {
check = true; // second filter based on previous recorded primes in array
break;
}
}
if (!check) {
e = a;
if (b <= 100) {
num[b] = a;
}
b = b + 1;
}
}
if ((b) == (prime - 4)) {
write << e << endl;
break;
}
}
}
}
trial.close();
write.close();
return 0;
}
나이 전적으로 기지에서 내 거짓 가이드고 자신을 그렇게 용서하는 코드를 비효율적으로 만들고,일반 초보자 ness 나의 알고리즘이 있습니다.또한 15 그것을 표시합니다 프라임 번호를 올바르게.
할 수 있는 사람을 말해 내가 어떻게 가야 개선에 대한 이 현재까요?나는 생각하고의 txt 파일을 사용하여 장소에서의 배열입니다.하는 것이 가능할까요?어떤 도움에 감사드립니다.
해결책 13
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
int main()
{
ifstream trial;
trial.open("C:\\Users\\User\\Documents\\trial.txt");
int prime, e;
trial>>prime;
ofstream write;
write.open("C:\\Users\\User\\Documents\\answer.txt");
int num[10000], currentPrime, c, primePrint;
bool check;
currentPrime=0;
num[currentPrime] = 2;
currentPrime=1;
for(int currentInt=2; currentInt<=1000000; currentInt++)
{check = false;
for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++)
{ c=num[arrayPrime];
if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
break;}
}
if (!check)
{ e=currentInt;
if( currentInt!= 2 ) {
num[currentPrime]= currentInt;}
currentPrime = currentPrime+1;}
if(currentPrime==prime)
{
write<<e<<endl;
break;}
}
trial.close();
write.close();
return 0;
}
이것은 원래 코드의 최종 버전 기반입니다. 완벽하게 작동하며 소수 범위를 늘리려면 배열 번호를 증가시킵니다. 도와 주셔서 감사합니다 =)
다른 팁
당신의 질문은 수학보다는 프로그래밍에 관한 것이므로, 나는 그렇게 대답을 그렇게 유지하려고 노력할 것입니다.
코드의 첫 번째 눈을 보면 지구상에서 무엇을하고 있는지 궁금해합니다 ... 답을 읽으면 일부는 코드를 이해하지 못하고 일부는 코드를 디버거에 버리는 것을 알게 될 것입니다. 그리고 무슨 일이 일어나고 있는지보십시오. 우리가 그렇게 참을성이 없는가? 아니면 단순히 코드가 비교적 쉬운 문제에 대해 이해하기가 너무 어렵습니까?
코드를 개선하려면 몇 가지 질문을 해보십시오.
- 무엇인가
a,b,c, 등? 더 의미있는 이름을주는 것이 더 낫지 않습니까? - 알고리즘은 정확히 무엇입니까? 당신은 당신이하고있는 일에 대해 (정확한 방식으로) 영어로 명확하게 쓰여진 단락을 적을 수 있습니까? 단락을 모든 입력을 정신적으로 수행 할 수있는 일련의 단계로 수정할 수 있고 그것이 올바른지 확인할 수 있습니까?
- 모든 단계가 필요한가요? 우리는 그들 중 일부를 결합하거나 제거 할 수 있습니까?
- 영어로 표현하기 쉽지만 C/C ++에서 10 줄 이상이 필요한 단계는 무엇입니까?
- 단계 목록에 구조가 있습니까? 루프? 하위 단계와 함께 단일 단계로 넣을 수있는 큰 (아마도 반복 된) 청크?
질문을 겪은 후에는 문제를 해결하는 의사 코드가 명확하게 배치되어 설명하고 이해하기 쉽습니다. 그 후에는 c/c ++ 또는 실제로 모든 범용 언어로 의사 코드를 구현할 수 있습니다.
가 있는 두 개의 접근 방식 테스트를 위한 최초를 고려할 수 있습니다:
- 문제 영역은 충분히 작은 것을 그냥 반복을 통해 번호를 찾을 때까지 번째 주요할 수 있을 것 수락가능한 솔루션을 보다 몇 밀리초를 완료합니다.의 수 있는 간단한 최적화할 수 있는 이 방법을 예를 들어,당신은 당신만을 필요로하는지 확인하는 테스트는 그것의 건 2 일단 그리고 당신은 단지 확인에 대한 이상한 숫자와 당신은 단지 확인하는 숫자보다 작거나 같 aquare 루트의 번호를 시험하고 있습니다.
- 에라토스테네스의 체 매우 효과적이고 및 쉽게 구현 및 수 없을 정도로 부드러운 수학에 대한 최종의 것이다.
으로는 이유에 대한 당신은 코드가 충돌이 생각 변화하는 줄을 읽
for( int d=0; d<=b; d++)
하기
for( int d=0; d<b; d++)
문제를 해결 하려고 하기 때문에서 읽은 잠재적으로 초기화되지 않은 배열의 요소는 아마도 포함 쓰레기입니다.
나는 당신의 코드를 보지 못했지만, 당신의 배열은 당신이 저장할 모든 값을 포함 할 수있을 정도로 커야합니다. 100은 확실히이 문제에 대한 대부분의 의견에 충분하지 않을 것입니다.
예 :이 코드 ..
int someArray[100];
someArray[150] = 10;
배열 (150> 100)보다 큰 위치에 씁니다. 이것을 메모리 덮어 쓰기라고합니다. 해당 메모리 위치에서 발생한 일에 따라 프로그램이 즉시, 나중에 또는 전혀 충돌 할 수 있습니다.
배열을 사용할 때의 모범 사례는 당신이 쓰는 요소가 배열의 범위 내에 있다고 어제 웨이에서 주장하는 것입니다. 또는이 확인을 수행하는 배열 형 클래스를 사용하십시오.
문제의 경우 가장 쉬운 방법은 STL 벡터 클래스를 사용하는 것입니다. 요소를 추가해야하지만 (vector :: push_back ())는 배열 연산자 []를 사용하여 나중에 요소에 액세스 할 수 있습니다. 벡터는 또한 최고의 반복 성능을 제공합니다.
다음은 벡터에 0-100을 추가 한 다음 인쇄하는 샘플 코드입니다. 참고 두 번째 루프에서는 벡터에 저장된 항목 수를 사용합니다.
#include <vector> // std::vector
...
const int MAX_ITEMS = 100;
std::vector<int> intVector;
intVector.reserve(MAX_ITEMS); // allocates all memory up-front
// add items
for (int i = 0; i < MAX_ITEMS; i++)
{
intVector.push_back(i); // this is how you add a value to a vector;
}
// print them
for (int i = 0; i < intVector.size(); i++)
{
int elem = intVector[i]; // this access the item at index 'i'
printf("element %d is %d\n", i, elem);
}
현재 기능 프로그래밍을 향상 시키려고 노력하고 있으므로 체를 빨리 코딩했습니다. 나는 여기에 게시 할 것이라고 생각한다. 여전히 배우고 있다면 흥미로울 수 있습니다.
#include <iostream>
#include <list>
#include <math.h>
#include <functional>
#include <algorithm>
using namespace std;
class is_multiple : public binary_function<int, int, bool>
{
public:
bool operator()(int value, int test) const
{
if(value == test) // do not remove the first value
return false;
else
return (value % test) == 0;
}
};
int main()
{
list<int> numbersToTest;
int input = 500;
// add all numbers to list
for(int x = 1; x < input; x++)
numbersToTest.push_back(x);
// starting at 2 go through the list and remove all multiples until you reach the squareroot
// of the last element in the list
for(list<int>::iterator itr = ++numbersToTest.begin(); *itr < sqrt((float) input); itr++)
{
int tmp = *itr;
numbersToTest.remove_if(bind2nd(is_multiple(), *itr));
itr = find(numbersToTest.begin(), numbersToTest.end(), tmp); //remove_if invalidates iterator
// so find it again. kind of ugly
}
// output primes
for(list<int>::iterator itr = numbersToTest.begin(); itr != --numbersToTest.end(); itr++)
cout << *itr << "\t";
system("PAUSE");
return 0;
}
그건 그렇고 이것을 개선하는 방법에 대한 조언은 환영받을 것입니다.
여기 내 코드가 있습니다. 큰 숫자로 작업 할 때는 매우 느립니다! 입력 한 숫자로 모든 소수를 계산할 수 있습니다!
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int main()
{
int m;
int n=0;
char ch;
fstream fp;
cout<<"What prime numbers do you want get within? ";
if((cin>>m)==0)
{
cout<<"Bad input! Please try again!\n";
return 1;
}
if(m<2)
{
cout<<"There are no prime numbers within "<<m<<endl;
return 0;
}
else if(m==2)
{
fp.open("prime.txt",ios::in|ios::out|ios::trunc);//create a file can be writen and read. If the file exist, it will be overwriten.
fp<<"There are only 1 prime number within 2.\n";
fp<<"2\n";
fp.close();
cout<<"Congratulations! It has worked out!\n";
return 0;
}
else
{
int j;
int sq;
fp.open("prime.txt",ios::in|ios::out|ios::trunc);
fp<<"2\t\t";
n++;
for(int i=3;i<=m;i+=2)
{
sq=static_cast<int>(sqrt(i))+1;
fp.seekg(0,ios::beg);
fp>>j;
for(;j<sq;)
{
if(i%j==0)
{
break;
}
else
{
if((fp>>j)==NULL)
{
j=3;
}
}
}
if(j>=sq)
{
fp.seekg(0,ios::end);
fp<<i<<"\t\t";
n++;
if(n%4==0)
fp<<'\n';
}
}
fp.seekg(0,ios::end);
fp<<"\nThere are "<<n<<" prime number within "<<m<<".\n";
fp.close();
cout<<"Congratulations! It has worked out!\n";
return 0;
}
}
우선, 3, 5 및 7에 대한 특별한 사례가 없다면 코드가 적습니다 (항상 좋은 일입니다!).
또한 NUM [B] = 2를 설정 한 경우 2의 특수 사례를 피하고 배열의 물건에 의한 분할 만 테스트 할 수 있습니다.
() 루프의 메인을 돌아 다니면서 B의 값이 증가합니다.
그런 다음 배열 끝에서 메모리에 액세스하기 때문에 충돌이 발생합니다.
for (int d = 0; d <= b; d++) {
c = num[d];
머리에 알고리즘을 더 명확하게하고 코드에 다시 접근해야한다고 생각합니다.
디버거를 통해 코드를 실행하면 플로팅 포인트 예외와 함께 충돌하는 것을 발견했습니다.if ((a % c) == 0)". 그 이유는 NUM에서 아무것도 초기화하지 않았으므로"A % 0 "을하고 있기 때문입니다.
내가 아는 바에 따르면 C/C ++ int는 16 비트 유형이므로 1 백만을 맞출 수 없습니다 (제한은 2^16 = 32k입니다). "A"를 오랫동안 시도하고 선언하십시오
C 표준이 그렇게 말합니다 int 적어도 크다 short 그리고 최대 큰 long.
실제로 int 4 바이트이므로 -2^31 그리고 2^31-1.
이것은 교육적 목적을위한 것이므로 구현을 제안합니다. Eratosthenes의 체.
이것은 또한 당신에게 관심이 있어야합니다. http://en.wikipedia.org/wiki/primality_test
for(int currentInt=2; currentInt<=1000000; currentInt++)
{check = false; // Basically the idea for this for loop is to run checks against integers. This is the main for loop in this program. I re initialize check to false ( check is a bool declared above this. )
for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++) // This for loop is used for checking the currentInt against previously found primes which are stored in the num array.
{ c=num[arrayPrime];
if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
break;} // this is the check. I check the number against every stored value in the num array. If it's divisible by any of them, then bool check is set to true.
if ( currentInt == 2)
{ check = false; } // since i preset num[0] = 2 i make an exception for the number 2.
if (!check)
{
e=a;
if(currentPrime <= 100){
num[currentPrime]= currentInt;} // This if uses check to see if the currentInt is a prime.
currentPrime = currentPrime+1;} // increases the value of currentPrime ( previously b ) by one if !check.
if(currentPrime==prime)
{
write<<e<<endl;
break;} // if currentPrime == prime then write the currentInt into a txt file and break loop, ending the program.
조언에 감사드립니다. polythinker =)
더 큰 소수 값이 필요하기 때문입니다 나중에 질문, 나는 당신이 Dreeves의 조언을 따르고 체를 수행하는 것이 좋습니다. 당신의 떨림에있는 것은 매우 유용한 화살입니다.
