первичная факторизация с использованием ситового метода

В вашем prime() Как правило, вы устанавливаете флаги, чтобы указать, является ли число простым или нет — те, которые с 1 в них не простые. Однако в primeFactorize функция, которую вы предполагаете, что массив p[] содержит значения простых чисел, а не флаг. Таким образом, вы очень скоро доберетесь до деления на ноль (так как флаг простого числа равен нулю), и вы потерпите крах.

Вы должны убедиться, что в массиве, к которому вы обращаетесь, есть ожидаемые числа!

Возможный подход заключается в создании двух массивов: pflags а также pvalues, Когда вы впервые проходите через установку флагов в вашем prime() функция, вы должны установить pflags, После того, как вы перебрали все возможные значения, вы очищаете массив pflags для нулевых значений; каждый раз, когда вы сталкиваетесь с одним, вы устанавливаете следующее значение pvalues к индексу pflags, Что-то вроде этого:

void prime(void)
{
long i,j;
pflags[0]=1;
pflags[1]=1;
for(i=2;i<=sqrt(SIZE);i++)  // prime generate part
if(pflags[i]==0)
for(j=2;j*i<SIZE;j++)
pflags[i*j]=1;
j=0;
for(i=0; i<SIZE; i++) {
if(flags[i]==0) pvalues[j++]=i;
}
}

Конечно, вы должны правильно инициализировать эти массивы и использовать pvalues вместо p в primeFactorize функция. Если вы умны, вы увидите, что на самом деле вы можете использовать тот же массив p для обеих этих вещей — но сложно держать в голове то, что ты делаешь, поэтому использование двух отдельных массивов поможет в понимании.

РЕДАКТИРОВАТЬ Я решил посмотреть, смогу ли я получить код для запуска — и он работает (после исправления одной опечатки, изменение scanf_s функция к scanfи исправление форматирования вывода из %d в %ld). Я также немного очистил ввод-вывод. Чтобы помочь вам, я включаю полный список, который работает для меня:

#include<iostream>
#include<cstdio>
#include<math.h>
#define SIZE 1000000
using namespace std;
long pvalues[SIZE], pflags[SIZE], input;
long List[SIZE];  // saves the List
long listSize;   // saves the size of Listvoid prime(void)
{
long i,j;
pflags[0]=1;
pflags[1]=1;
for(i=2;i<=sqrt(SIZE);i++)  // prime generate part
if(pflags[i]==0)
for(j=2;j*i<SIZE;j++)
pflags[i*j]=1;
j=0;
for(i=0; i<SIZE; i++) {
if(pflags[i]==0) pvalues[j++]=i;
}
}
void primeFactorize( long n )
{
listSize = 0;   // Initially the List is empty, we denote that size = 0
long sqrtN = long( sqrt(n) ); // find the sqrt of the number
for( long i = 0; pvalues[i] <= sqrtN; i++ ) { // we check up to the sqrt
if( n % pvalues[i] == 0 ) { // n is multiple of prime[i]
// So, we continue dividing n by prime[i] as long as possible
while( n % pvalues[i] == 0 ) {
n /= pvalues[i]; // we have divided n by prime[i]
List[listSize] = pvalues[i]; // added the ith prime in the list
listSize++; // added a prime, so, size should be increased
}
// we can add some optimization by updating sqrtN here, since n
// is decreased. think why it's important and how it can be added
}
}
if( n > 1 )
{
// n is greater than 1, so we are sure that this n is a prime
List[listSize] = n; // added n (the prime) in the list
listSize++; // increased the size of the list
}
}

int main(void)
{
prime();
printf("\nEnter number to factorize: ");
while(scanf("%ld",&input),input)
{
if(input==1)
printf("1 = 1\n");
else if(input==-1)
printf("-1 = -1 x 1\n");
else
{
primeFactorize( input );

}
printf("The number %ld has the following factors: ", input);
for( long i = 0; i < listSize; i++ ) // traverse the List array
printf("%ld ", List[i]);
printf("\n\nEnter number to factorize: ");

}
return 0;
}

Я проверил это для нескольких разных входов:

Enter number to factorize: 81
The number 81 has the following factors: 3 3 3 3

Enter number to factorize: 123
The number 123 has the following factors: 3 41

Enter number to factorize: 64
The number 64 has the following factors: 2 2 2 2 2 2

Enter number to factorize: 0

(exits)

Все именно так, как и ожидалось.