Программа для простых чисел
https://stackoverflow.com/questions/502443
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
В настоящее время я пробую ответить на несколько вопросов, просто чтобы попрактиковаться в своих навыках программирования.(Пока не изучал это в школе или что-то еще, самоучка) Я столкнулся с этой проблемой, которая потребовала, чтобы я прочитал номер из заданного текстового файла.Это число будет равно N.Теперь я предполагаю найти N-е простое число для N <= 10 000.После того, как я найду его, я должен распечатать его в другой текстовый файл.Теперь по большей части вопроса я могу понять и разработать метод получения N.Проблема в том, что я использую массив для сохранения ранее найденных простых чисел, чтобы использовать их для сверки с будущими числами.Даже когда мой массив имел размер 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;
}
Я сделал это полностью на основе моего руководства для чайников и самого себя, так что прошу простить некоторую неэффективность кода и общую новизну моего алгоритма.Также для чисел до 15 он корректно отображает простые числа.
Кто-нибудь может сказать мне, как мне следует улучшить этот текущий код?Я подумываю об использовании текстового файла вместо массива.Возможно ли это?Любая помощь приветствуется.
Решение 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, и т.д.?Не лучше ли было бы дать более значимые имена? - В чем именно заключается ваш алгоритм?Можете ли вы записать четко написанный абзац на английском языке о том, что вы делаете (точным способом)?Можете ли вы преобразовать абзац в серию шагов, которые вы можете мысленно выполнить для любого ввода и быть уверенными, что он правильный?
- Все ли шаги необходимы?Можем ли мы объединить или даже исключить некоторые из них?
- Какие шаги легко выразить на английском языке, но требуют, скажем, более 10 строк на C / C ++?
- Есть ли в вашем списке шагов какие-либо структуры?Петли?Большие (вероятно, повторяющиеся) куски, которые можно поместить как один шаг с подэтап?
После того, как вы разберетесь с вопросами, у вас, вероятно, будет четко изложенный псевдокод, решающий проблему, который легко объяснить и понять.После этого вы можете реализовать свой псевдокод на C / C ++ или, фактически, на любом языке общего назначения.
Существует два подхода к тестированию на простоту, которые вы, возможно, захотите рассмотреть:
- Проблемная область достаточно мала, так что простое перебирание чисел до тех пор, пока вы не найдете N-е простое число, вероятно, было бы приемлемым решением и заняло бы менее нескольких миллисекунд для завершения.Есть ряд простых оптимизаций, которые вы можете внести в этот подход, например, вам нужно только один раз проверить, делится ли оно на 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()), вы можете позже получить доступ к элементам, используя оператор массива [].Vector также обеспечит вам наилучшую итеративную производительность.
Вот несколько примеров кода добавления чисел 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;
}
Кстати, я был бы рад любым советам о том, как это улучшить.
Вот мой код.При работе с большим числом это происходит очень медленно!Он может вычислять все простые числа с помощью in введенного вами числа!
#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.
Кроме того, вы можете избежать особого случая для 2, если вы просто установите num[b] = 2 и будете проверять делимость только по элементам в вашем массиве.
Похоже, что по мере того, как вы обходите основной цикл for(), значение 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.
Поскольку это делается в педагогических целях, я бы предложил внедрить решето Эратосфена.
Это также должно вас заинтересовать: 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.
Спасибо за совет, политинкер =)
Поскольку вам понадобятся большие значения простых чисел для последующие вопросы, Я предлагаю вам последовать совету Дривза и сделать сито.Это очень полезная стрела, которую нужно иметь в своем колчане.
