在C语言中素数 [英] Prime numbers in c language
问题描述
我想找到与多线程和使用E. function.I筛写一些片codeS素数。如果程序运行时，用户输入一个最大数和线程数。该方案应该创建给定的线程数目的线程。该程序查找所有质数，直到最大数量。每个线程都必须选中一个素数。
我的程序没有找到素数。我写checkPrime功能，crossout功能有效地寻找素数。但是，这是行不通的。所以，我无法检查线程正确与否工作。我怎样才能实现checkPrime功能？
有3个功能。 crossout是筛法E.。 checkPrime为检查是一个数字素或没有。工人是线程的功能。每个线程都必须选中一个素数。
的#include＆LT;＆stdlib.h中GT;
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆string.h中GT;
＃包括LT＆;＆pthreads.h中GT;＃定义MAX_N亿
max_threads的的#define 25//全局值
INT threadNumber;
INT largestNumber;
INT isPrime;
INT来确定nthreads，//线程数（不包括主要的（））
素[MAX_N + 1〕，
N，//最后，总理由[i] = 1，如果我素，否则为0
NEXTBASE; //要使用的下一个筛子倍增//锁共享变量NEXTBASE
pthread_mutex_t nextbaselock = PTHREAD_MUTEX_INITIALIZER;无效crossout（int类型的）{
INT I，J，检查;
对于（i = 2; I＆LT; largestNumber;我++）
素[I] = 1; 对于（I = A; I＆LT; largestNumber;）
如果（主要由[i]）
为（J =我;我* J＆LT; largestNumber; J ++）
黄金[我* J] = 0;}INT checkPrime（int类型的）{
INT I;
对于（i = 2; I＆LT = A ++我）{
如果（A％I == 0）{
isPrime = 1;
返回isPrime;
打破;
}其他
isPrime = 2;
crossout（一）;
返回isPrime;
}
}无效*的WorkerThread（无效* T）{ INT廉，基地; 长I，J;
长TID; TID =（长）吨;
的printf（线程％ld的起点...... \\ n，TID）; 而（1）{
调用pthread_mutex_lock（安培; nextbaselock）;
基地= NEXTBASE;
NEXTBASE ++;
//解开锁
调用pthread_mutex_unlock（安培; nextbaselock）;
如果（基本和LT = LIM）{ 如果（主要基地】）{
checkPrime（基峰）;
//工作日志本线程完成
}
}
如果（checkPrime（基峰）== 2）
的printf（线程％ld的做首相=％d个\\ n，TID基地）;
了pthread_exit（（无效*）T）;
} 返回NULL;
}//有两个参数主要功能：argc和argv
INT主（INT ARGC，字符** argv的）{ threadNumber = argv的[3];
largestNumber =的argv [1];
INT I; 线程的pthread_t [threadNumber]
INT RC;
长吨;
void *的状态; 对于（t = 0; T＆LT; threadNumber;吨++）{
的printf（主营：创建线程％LD \\ n，T）;
RC =在pthread_create（安培;螺纹[T]，NULL，的WorkerThread，（无效*）T）;
如果（RC）{
的printf（ERROR;从pthread_create的收益code（）为％d \\ n，RC）;
出口（-1）;
}
} 对于（t = 0; T＆LT; threadNumber;吨++）{
RC =在pthread_join（线程[T]，（无效*）＆amp; T公司）;
如果（RC）{
的printf（ERROR;从在pthread_join返回code（）为％d \\ n，RC）;
出口（-1）;
}
的printf（主营：完成加盟螺纹％LD \\ n，T）;
}
}
您正试图混寻找素数两种不同的方法。你并不需要同时使用迭代划分方法 和的的埃拉托色尼筛。此示出了实现了筛的方法。偶数在筛忽略，但作为特殊情况在处理isprime（）。但它不会帮助你找到一个多线程解决方案，因为你不能仅仅交出不同的号码，以不同的线程 - 每个主要建立在previous首要的工作，首先是假设 3 为素数。
//埃拉托色尼筛
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;的#define LIMIT 200焦炭筛[LIMIT] = {1，1，}; // 1不贷INT isprime（无符号N）
{
如果（N下; = 2）//特殊情况
返回筛[N] == 0;
如果（N％2 == 0）//连号是不是素数
返回0;
如果（N＆GT; = LIMIT）//测试范围
出口（1）;
返回筛[N] == 0;
}INT主要（无效）
{
无符号的N，P;
为（N = 3; N＆LT;极限; N + = 2）{//奇数只有数字
如果（筛[N] == 0）{//如果n是素数
为（P = N * N，P＆LT;限制; P + = N * 2）{//忽略偶数
筛[P] = 1; //不primne
}
}
} 的printf（素数：\\ n）;
为（N = 0; N＆LT;极限; N ++）{//检查所有的数字
如果（isprime（N））{//如果n是素数
的printf（％ - 四维，N）;
}
}
的printf（\\ n）;
返回0;
}
程序输出：
素数：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199
我现在会显示一个迭代的划分方法。再一次，即使数字被视为特殊情况。我不经常写多线程C code，所以我不能帮你。但我希望你能建立在第二个例子做一个多线程的解决方案。
//迭代师
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆math.h中GT;的#define LIMIT 200INT isprime（无符号N）
{
无符号的S，I;
如果（N下; = 1）
返回0;
如果（N == 2）
返回1;
如果（N％2 == 0）//无连号
返回0;
S =（符号）的sqrt（N）; //限制环路
对于（i = 3; I＆LT; = S，I + = 2）//奇数只
如果（N％我== 0）
返回0;
返回1;
}INT主要（无效）
{
无符号N;
的printf（素数：\\ n）;
为（N = 0; N＆LT;极限; N ++）{//检查所有的数字
如果（isprime（N））{//如果n是素数
的printf（％ - 四维，N）;
}
}
的printf（\\ n）;
返回0;
}
程序输出：
素数：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199
有一些缺陷在上面的两个例子有较大的数字时，我会留下来给你来发现。
I want to find prime numbers with multithreading and using Sieve of E. function.I write some piece of codes. If the program will run, the user enter a max number and thread number. The program should create threads that given thread number. The program find all prime numbers until the max number. Each thread must check one prime number.
My program doesn't find prime numbers. I write checkPrime function and crossout functions for finding prime numbers efficiently. But it doesn't work. So, I can't check my threads work correctly or not. How can I implement checkPrime function?
There are 3 functions. crossout is for Sieve E. method. checkPrime is for checking is a number prime or not. worker is for thread's function. Each thread must check one prime number.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <pthread.h>
#define MAX_N 100000000
#define MAX_THREADS 25
// global values
int threadNumber;
int largestNumber;
int isPrime;
int nthreads, // number of threads (not counting main())
prime[MAX_N + 1],
n, // in the end, prime[i] = 1 if i prime, else 0
nextbase; // next sieve multiplier to be used
// lock for the shared variable nextbase
pthread_mutex_t nextbaselock = PTHREAD_MUTEX_INITIALIZER;
void crossout(int a) {
int i, j, check;
for (i = 2; i < largestNumber; i++)
prime[i] = 1;
for (i = a; i < largestNumber;)
if (prime[i])
for (j = i; i * j < largestNumber; j++)
prime[i * j] = 0;
}
int checkPrime(int a) {
int i;
for (i = 2; i <= a; ++i) {
if (a % i == 0) {
isPrime = 1;
return isPrime;
break;
} else
isPrime = 2;
crossout(a);
return isPrime;
}
}
void* workerThread(void* t) {
int lim, base;
long i, j;
long tid;
tid = (long)t;
printf("Thread %ld starting...\n", tid);
while (1) {
pthread_mutex_lock(&nextbaselock);
base = nextbase;
nextbase++;
// unlock the lock
pthread_mutex_unlock(&nextbaselock);
if (base <= lim) {
if (prime[base]) {
checkPrime(base);
// log work done by this thread
}
}
if (checkPrime(base) == 2)
printf("Thread %ld done. Prime = %d\n", tid, base);
pthread_exit((void*) t);
}
return NULL;
}
//main function with two parameters :argc and argv
int main(int argc, char** argv) {
threadNumber = argv[3];
largestNumber = argv[1];
int i;
pthread_t thread[threadNumber];
int rc;
long t;
void* status;
for (t = 0; t < threadNumber; t++) {
printf("Main: creating thread %ld\n", t);
rc = pthread_create(&thread[t], NULL, workerThread, (void*)t);
if (rc) {
printf("ERROR; return code from pthread_create() is %d\n", rc);
exit(-1);
}
}
for (t = 0; t < threadNumber; t++) {
rc = pthread_join(thread[t], (void*)&t);
if (rc) {
printf("ERROR; return code from pthread_join() is %d\n", rc);
exit(-1);
}
printf("Main: completed join with thread %ld \n", t);
}
}
You are trying to mix two different methods for finding prime numbers. You don't need to use both the iterative division method and the sieve of Eratosthenes. This shows a way of implementing the sieve. Even numbers are ignored in the sieve but treated as special cases in isprime(). But it won't help you find a multi threaded solution, because you can't just hand over different numbers to different threads - each prime builds on the work of the previous prime, starting with the assumption that 3 is prime.
// Sieve of Eratosthenes
#include <stdio.h>
#include <stdlib.h>
#define LIMIT 200
char sieve[LIMIT] = { 1, 1, }; // 1 for not-prime
int isprime(unsigned n)
{
if(n <= 2) // special cases
return sieve[n] == 0;
if(n % 2 == 0) // even numbers are not prime
return 0;
if(n >= LIMIT) // test range
exit(1);
return sieve[n] == 0;
}
int main(void)
{
unsigned n, p;
for(n=3; n<LIMIT; n+=2) { // odd numbers only
if (sieve[n] == 0) { // if n is prime
for(p=n*n; p<LIMIT; p+=n*2) { // ignore even numbers
sieve[p] = 1; // not primne
}
}
}
printf("Prime numbers are:\n");
for(n=0; n<LIMIT; n++) { // check all numbers
if (isprime(n)) { // if n is prime
printf("%-4d", n);
}
}
printf("\n");
return 0;
}
Program output:
Prime numbers are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199
I'll now show an iterative division method. Once again, even numbers are treated as special cases. I don't often write multi threaded C code, so I can't help you with that. But I hope you can build on this second example to make a multi threaded solution.
// iterative division
#include <stdio.h>
#include <math.h>
#define LIMIT 200
int isprime(unsigned n)
{
unsigned s, i;
if(n <= 1)
return 0;
if(n == 2)
return 1;
if(n % 2 == 0) // no even numbers
return 0;
s = (unsigned)sqrt(n); // limit the loop
for(i=3; i<=s; i+=2) // odd numbers only
if (n % i == 0)
return 0;
return 1;
}
int main(void)
{
unsigned n;
printf("Prime numbers are:\n");
for(n=0; n<LIMIT; n++) { // check all numbers
if (isprime(n)) { // if n is prime
printf("%-4d", n);
}
}
printf("\n");
return 0;
}
Program output:
Prime numbers are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199
There are some pitfalls in both of the above examples when working with larger numbers, but I'll leave them for you to discover.
这篇关于在C语言中素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
