c - 素数生成器

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

有关您编写的代码问题的问题必须在问题本身中描述具体问题 - 并包含有效代码以重现该问题。请参阅SSCCE.org寻求指导。

已关闭 9 年前。

Improve this question

http://www.spoj.com/problems/PRIME1/所以这是我应该解决的任务，我试图解决它但失败了。我已经编写了几个代码，但没有一个工作得足够好，但我的最后一个代码让我感到惊讶，因为它无缘无故地显示了随机的废话。这是用 C 编写的代码。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(){
    int i=0,r=0,j,t,n,m,koren,f,pom;   /*koren=square root, pom=tmp rez=solution*/
    int rez [100];
    scanf("%d \n", &t);
    for(i=0;i<=t;i++){
        scanf("%d%d \n",&n,&m);
        if (n%2==0)
        {
                n+=1;
        } /* it is supposed to skip every even number */
        for(j=n;j<=m;j=j+2){
           koren=round(sqrt(j));
        for(f=2;f<=koren;f++){
               if (j % f != 0){pom=j;}else{pom=0;break;}
           }
           if(pom>0){rez[r]=pom;r++;}    
        }
    }
    for (i=0;i<=r;i++)
    {
            printf("%d \n",&rez[i]);
    }
    return 0;
}

任何建议和帮助将不胜感激。

如果我在语言上犯了任何错误，我很抱歉，这不是我的母语。

Answer 1

你可以检查这个质数生成器的c代码:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>

#define NUMITERS 200
#define MAXSIZE 500000
#define MAXNUMPROCS 64
#define PRIME(num) (2*(num) + 3)
#define NUM(prime) (((prime) - 3)/2)

#define TRUE 1
#define FALSE 0

int lastPrime, count;      /* Last Prime and Number of Primes Found */
int size = 1000;           /* Number of numbers to test for prime */
int numProcs = 1;          /* Number of processors */
FILE *out = NULL;          /* File to output primes to */
char *flags;               /* Array of primes (odd numbers only) 
                              i.e. flags[0] corresponds to 3
                              flags[1] corresponds to 5
                              flags[n] corresponds to 2*n+3
                              flags[i] is TRUE if i is a prime */

void primes(void);              /* procedure prototype */
void parallelPrimes(void);      /* procedure prototype */


/**
 * prints the usage instructions and exits
 */
void usage(char *filename) {
  printf("Usage: %s <flags>\n", filename);
  printf("\t-m <num>\tMaximum number to test\n");
  printf("\t-p <num>\tNumber of processors being run on\n");
  printf("\t-o <filename>\tFilename to output primes to\n");
  printf("\t-s\t\tOutput primes to stdout\n");
  printf("\t-h\t\tDisplay these usage instructions\n");
  exit(0);
}

/**
 * main routine:
 *
 */

int main(int argc, char *argv[])
{
    int i;
    int opt;

    do {
      char *test;
      opt = getopt(argc, argv, "p:m:o:sh");

      switch (opt) {
      case 'p':
    numProcs = atoi(optarg);

    if (numProcs < 1 || numProcs > MAXNUMPROCS) {
      printf("Invalid number of processors -- %d\n\n", numProcs);
      usage(argv[0]);
    }

    break; 

      /* set maximum number to test */
      case 'm':
    size = NUM(atoi(optarg));

    if (size < 0 || size > MAXSIZE) {
      printf("Invalid maximum number to test -- %d\n\n", size);
      usage(argv[0]);
    }
    break;

      /* select outputing the primes to stdout */
      case 's': 
    if (out != NULL) {
      printf("multiple output locations is unsupported\n\n");
      usage(argv[0]);
    }

    out = stdout;
    break;

      /* set the file to output the primes to */
      case 'o':
    if (out != NULL) {
      printf("multiple output locations is unsupported\n\n");
      usage(argv[0]);
    }

    out = fopen(optarg, "w");
    if (out == NULL) {
      printf("Unable to open \"%s\"\n\n", optarg);
      usage(argv[0]);
    }
    break;

      /* help */
      case 'h':
    usage(argv[0]);
    break;

      /* unknown argument */
      case '?':
    usage(argv[0]);
    break;

      /* -1, we're done */
      default:
    break;
      }
    } while(opt > 0);

    if (optind < argc) {
      printf("Unknown argument -- %s\n\n", argv[optind]);
      usage(argv[0]);
    }

    printf("  Prime Generator (testing %d numbers, %d iterations on %d procs)\n", 
           size, NUMITERS, numProcs);

    flags = (char *) malloc(size * sizeof( char ) );
    if (!flags) {
        printf("\n   Could Not Allocate Memory for Array Size: %d\n",size);
        exit(1); 
    }

    if (numProcs == 1) 
      primes();   /* Call our primes routine */
    else
      parallelPrimes();

    /* print out all of the primes found */
    if (out != NULL) {
      int i;
      fprintf(out, "2\n");
      for (i = 0; i < size; ++i)
    if (flags[i])
      fprintf(out, "%d\n", PRIME(i));
    }

    free(flags);
    printf(" Number of primes = %d, largest prime = %d\n", count, lastPrime);
}


/**
 * primes: single-threaded prime number searching routine. 
 *
 * We test each odd number n to see if it's prime by dividing
 * by all smaller primes <= sqrt(n) and checking to see if the remainer
 * is zero.
 */
void primes()
{
    int i;
    int iter, prime;
    int div1, div2, rem;

    for (iter=0; iter < NUMITERS; ++iter)      
        {
            count = 0;
            lastPrime = 0;

            for (i=0; i < size; ++i) {    /* For every odd number */
            prime = PRIME(i);              

                /* Keep searching for divisor until rem == 0 (i.e. non prime),
                   or we've reached the sqrt of prime (when div1 > div2) */

                div1=1;
                do {                            
                    div1 += 2;            /* Divide by 3, 5, 7, ... */
            div2 = prime / div1;  /* Find the dividend */
            rem = prime % div1;   /* Find remainder */
                } while (rem != 0 && div1 <= div2); 

                if (rem != 0 || div1 == prime) {
                    /* prime is really a prime */

                    flags[i] = TRUE;
                    count++;                   
                    lastPrime = prime;
                } else {
                    /* prime is not a prime */
                    flags[i] = FALSE;         
                }
            }
        }
}


/**
 * parallelPrimes: multi-threaded prime number searching routine. 
 *
 * We test each odd number n to see if it's prime by dividing
 * by all smaller primes <= sqrt(n) and checking to see if the remainer
 * is zero.
 */
void parallelPrimes()
{
    // TODO: Parallelize this function 
    // You may find the numProcs global variable to be useful here

    int i;
    int iter, prime;
    int div1, div2, rem;

    for (iter=0; iter < NUMITERS; ++iter)      
        /* This is just to make running time reasonable. 
           Don't parallelize this loop */
        {
            count = 0;
            lastPrime = 0;

            for (i=0; i < size; ++i) {    /* For every odd number */
            prime = PRIME(i);              

                /* Keep searching for divisor until rem == 0 (i.e. non prime),
                   or we've reached the sqrt of prime (when div1 > div2) */

                div1=1;
                do {                            
                    div1 += 2;            /* Divide by 3, 5, 7, ... */
            div2 = prime / div1;  /* Find the dividend */
            rem = prime % div1;   /* Find remainder */
                } while (rem != 0 && div1 <= div2); 

                if (rem != 0 || div1 == prime) {
                    /* prime is really a prime */

                    flags[i] = TRUE;
                    count++;                   
                    lastPrime = prime;
                } else {
                    /* prime is not a prime */
                    flags[i] = FALSE;         
                }
            }
        }
}